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  - 
TY  - JOUR
A1  - Fichte, Johannes Klaus
A1  - Szeider, Stefan
T1  - Backdoors to tractable answer set programming
JF  - Artificial intelligence
N2  - Answer Set Programming (ASP) is an increasingly popular framework for declarative programming that admits the description of problems by means of rules and constraints that form a disjunctive logic program. In particular, many Al problems such as reasoning in a nonmonotonic setting can be directly formulated in ASP. Although the main problems of ASP are of high computational complexity, complete for the second level of the Polynomial Hierarchy, several restrictions of ASP have been identified in the literature, under which ASP problems become tractable.
 In this paper we use the concept of backdoors to identify new restrictions that make ASP problems tractable. Small backdoors are sets of atoms that represent "clever reasoning shortcuts" through the search space and represent a hidden structure in the problem input. The concept of backdoors is widely used in theoretical investigations in the areas of propositional satisfiability and constraint satisfaction. We show that it can be fruitfully adapted to ASP. We demonstrate how backdoors can serve as a unifying framework that accommodates several tractable restrictions of ASP known from the literature. Furthermore, we show how backdoors allow us to deploy recent algorithmic results from parameterized complexity theory to the domain of answer set programming. (C) 2015 Elsevier B.V. All rights reserved.
KW  - Answer set programming
KW  - Backdoors
KW  - Computational complexity
KW  - Parameterized complexity
KW  - Kernelization
Y1  - 2015
U6  - https://doi.org/10.1016/j.artint.2014.12.001
SN  - 0004-3702
SN  - 1872-7921
VL  - 220
SP  - 64
EP  - 103
PB  - Elsevier
CY  - Amsterdam
ER  -