@article{CaselFischbeckFriedrichetal.2022,
  author    = {Casel, Katrin and Fischbeck, Philipp and Friedrich, Tobias and G{\"o}bel, Andreas and Lagodzinski, J. A. Gregor},
  title     = {Zeros and approximations of Holant polynomials on the complex plane},
  series = {Computational complexity : CC},
  volume    = {31},
  journal   = {Computational complexity : CC},
  number    = {2},
  publisher = {Springer},
  address   = {Basel},
  issn      = {1016-3328},
  doi       = {10.1007/s00037-022-00226-5},
  pages     = {52},
  year      = {2022},
  abstract  = {We present fully polynomial time approximation schemes for a broad class of Holant problems with complex edge weights, which we call Holant polynomials. We transform these problems into partition functions of abstract combinatorial structures known as polymers in statistical physics. Our method involves establishing zero-free regions for the partition functions of polymer models and using the most significant terms of the cluster expansion to approximate them. Results of our technique include new approximation and sampling algorithms for a diverse class of Holant polynomials in the low-temperature regime (i.e. small external field) and approximation algorithms for general Holant problems with small signature weights. Additionally, we give randomised approximation and sampling algorithms with faster running times for more restrictive classes. Finally, we improve the known zero-free regions for a perfect matching polynomial.},
  language  = {en}
}
@article{CaselFernauGaspersetal.2020,
  author    = {Casel, Katrin and Fernau, Henning and Gaspers, Serge and Gras, Benjamin and Schmid, Markus L.},
  title     = {On the complexity of the smallest grammar problem over fixed alphabets},
  series = {Theory of computing systems},
  volume    = {65},
  journal   = {Theory of computing systems},
  number    = {2},
  publisher = {Springer},
  address   = {New York},
  issn      = {1432-4350},
  doi       = {10.1007/s00224-020-10013-w},
  pages     = {344 -- 409},
  year      = {2020},
  abstract  = {In the smallest grammar problem, we are given a word w and we want to compute a preferably small context-free grammar G for the singleton language {w} (where the size of a grammar is the sum of the sizes of its rules, and the size of a rule is measured by the length of its right side). It is known that, for unbounded alphabets, the decision variant of this problem is NP-hard and the optimisation variant does not allow a polynomial-time approximation scheme, unless P = NP. We settle the long-standing open problem whether these hardness results also hold for the more realistic case of a constant-size alphabet. More precisely, it is shown that the smallest grammar problem remains NP-complete (and its optimisation version is APX-hard), even if the alphabet is fixed and has size of at least 17. The corresponding reduction is robust in the sense that it also works for an alternative size-measure of grammars that is commonly used in the literature (i. e., a size measure also taking the number of rules into account), and it also allows to conclude that even computing the number of rules required by a smallest grammar is a hard problem. On the other hand, if the number of nonterminals (or, equivalently, the number of rules) is bounded by a constant, then the smallest grammar problem can be solved in polynomial time, which is shown by encoding it as a problem on graphs with interval structure. However, treating the number of rules as a parameter (in terms of parameterised complexity) yields W[1]-hardness. Furthermore, we present an O(3(vertical bar w vertical bar)) exact exponential-time algorithm, based on dynamic programming. These three main questions are also investigated for 1-level grammars, i. e., grammars for which only the start rule contains nonterminals on the right side; thus, investigating the impact of the "hierarchical depth" of grammars on the complexity of the smallest grammar problem. In this regard, we obtain for 1-level grammars similar, but slightly stronger results.},
  language  = {en}
}
@article{CaselFernauGhadikolaeietal.2022,
  author    = {Casel, Katrin and Fernau, Henning and Ghadikolaei, Mehdi Khosravian and Monnot, Jerome and Sikora, Florian},
  title     = {On the complexity of solution extension of optimization problems},
  series = {Theoretical computer science : the journal of the EATCS},
  volume    = {904},
  journal   = {Theoretical computer science : the journal of the EATCS},
  publisher = {Elsevier},
  address   = {Amsterdam [u.a.]},
  issn      = {0304-3975},
  doi       = {10.1016/j.tcs.2021.10.017},
  pages     = {48 -- 65},
  year      = {2022},
  abstract  = {The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating minimal vertex covers of a graph G = (V, E), one usually arrives at the problem to decide for a vertex set U subset of V (pre-solution), if there exists a minimal vertex cover S (i.e., a vertex cover S subset of V such that no proper subset of S is a vertex cover) with U subset of S (minimal extension of U). We propose a general, partial-order based formulation of such extension problems which allows to model parameterization and approximation aspects of extension, and also highlights relationships between extension tasks for different specific problems. As examples, we study a number of specific problems which can be expressed and related in this framework. In particular, we discuss extension variants of the problems dominating set and feedback vertex/edge set. All these problems are shown to be NP-complete even when restricted to bipartite graphs of bounded degree, with the exception of our extension version of feedback edge set on undirected graphs which is shown to be solvable in polynomial time. For the extension variants of dominating and feedback vertex set, we also show NP-completeness for the restriction to planar graphs of bounded degree. As non-graph problem, we also study an extension version of the bin packing problem. We further consider the parameterized complexity of all these extension variants, where the parameter is a measure of the pre-solution as defined by our framework.},
  language  = {en}
}
@article{CaselDreierFernauetal.2020,
  author    = {Casel, Katrin and Dreier, Jan and Fernau, Henning and Gobbert, Moritz and Kuinke, Philipp and Villaamil, Fernando S{\´a}nchez and Schmid, Markus L. and van Leeuwen, Erik Jan},
  title     = {Complexity of independency and cliquy trees},
  series = {Discrete applied mathematics},
  volume    = {272},
  journal   = {Discrete applied mathematics},
  publisher = {Elsevier},
  address   = {Amsterdam [u.a.]},
  issn      = {0166-218X},
  doi       = {10.1016/j.dam.2018.08.011},
  pages     = {2 -- 15},
  year      = {2020},
  abstract  = {An independency (cliquy) tree of an n-vertex graph G is a spanning tree of G in which the set of leaves induces an independent set (clique). We study the problems of minimizing or maximizing the number of leaves of such trees, and fully characterize their parameterized complexity. We show that all four variants of deciding if an independency/cliquy tree with at least/most l leaves exists parameterized by l are either Para-NP- or W[1]-hard. We prove that minimizing the number of leaves of a cliquy tree parameterized by the number of internal vertices is Para-NP-hard too. However, we show that minimizing the number of leaves of an independency tree parameterized by the number k of internal vertices has an O*(4(k))-time algorithm and a 2k vertex kernel. Moreover, we prove that maximizing the number of leaves of an independency/cliquy tree parameterized by the number k of internal vertices both have an O*(18(k))-time algorithm and an O(k 2(k)) vertex kernel, but no polynomial kernel unless the polynomial hierarchy collapses to the third level. Finally, we present an O(3(n) . f(n))-time algorithm to find a spanning tree where the leaf set has a property that can be decided in f (n) time and has minimum or maximum size.},
  language  = {en}
}