TY  - JOUR
A1  - Casel, Katrin
A1  - Fernau, Henning
A1  - Ghadikolaei, Mehdi Khosravian
A1  - Monnot, Jerome
A1  - Sikora, Florian
T1  - On the complexity of solution extension of optimization problems
JF  - Theoretical computer science : the journal of the EATCS
N2  - 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.
KW  - extension problems
KW  - NP-hardness
KW  - parameterized complexity
Y1  - 2022
U6  - https://doi.org/10.1016/j.tcs.2021.10.017
SN  - 0304-3975
SN  - 1879-2294
VL  - 904
SP  - 48
EP  - 65
PB  - Elsevier
CY  - Amsterdam [u.a.]
ER  - 
TY  - JOUR
A1  - Casel, Katrin
A1  - Dreier, Jan
A1  - Fernau, Henning
A1  - Gobbert, Moritz
A1  - Kuinke, Philipp
A1  - Villaamil, Fernando Sánchez
A1  - Schmid, Markus L.
A1  - van Leeuwen, Erik Jan
T1  - Complexity of independency and cliquy trees
JF  - Discrete applied mathematics
N2  - 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.
KW  - independency tree
KW  - cliquy tree
KW  - parameterized complexity
KW  - Kernelization
KW  - algorithms
KW  - exact algorithms
Y1  - 2018
U6  - https://doi.org/10.1016/j.dam.2018.08.011
SN  - 0166-218X
SN  - 1872-6771
VL  - 272
SP  - 2
EP  - 15
PB  - Elsevier
CY  - Amsterdam [u.a.]
ER  -