@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}
}
@article{FichteSzeider2015,
  author    = {Fichte, Johannes Klaus and Szeider, Stefan},
  title     = {Backdoors to tractable answer set programming},
  series = {Artificial intelligence},
  volume    = {220},
  journal   = {Artificial intelligence},
  publisher = {Elsevier},
  address   = {Amsterdam},
  issn      = {0004-3702},
  doi       = {10.1016/j.artint.2014.12.001},
  pages     = {64 -- 103},
  year      = {2015},
  abstract  = {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.},
  language  = {en}
}