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 - Blaesius, Thomas A1 - Friedrich, Tobias A1 - Schirneck, Friedrich Martin T1 - The complexity of dependency detection and discovery in relational databases JF - Theoretical computer science N2 - Multi-column dependencies in relational databases come associated with two different computational tasks. The detection problem is to decide whether a dependency of a certain type and size holds in a given database, the discovery problem asks to enumerate all valid dependencies of that type. We settle the complexity of both of these problems for unique column combinations (UCCs), functional dependencies (FDs), and inclusion dependencies (INDs). We show that the detection of UCCs and FDs is W[2]-complete when parameterized by the solution size. The discovery of inclusion-wise minimal UCCs is proven to be equivalent under parsimonious reductions to the transversal hypergraph problem of enumerating the minimal hitting sets of a hypergraph. The discovery of FDs is equivalent to the simultaneous enumeration of the hitting sets of multiple input hypergraphs. We further identify the detection of INDs as one of the first natural W[3]-complete problems. The discovery of maximal INDs is shown to be equivalent to enumerating the maximal satisfying assignments of antimonotone, 3-normalized Boolean formulas. KW - data profiling KW - enumeration complexity KW - functional dependency KW - inclusion KW - dependency KW - parameterized complexity KW - parsimonious reduction KW - transversal hypergraph KW - Unique column combination KW - W[3]-completeness Y1 - 2021 U6 - https://doi.org/10.1016/j.tcs.2021.11.020 SN - 0304-3975 SN - 1879-2294 VL - 900 SP - 79 EP - 96 PB - Elsevier CY - Amsterdam 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 -