Complexity of independency and cliquy trees
- 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 thirdAn 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.…
Verfasserangaben: | Katrin CaselORCiDGND, Jan DreierORCiDGND, Henning FernauORCiDGND, Moritz GobbertGND, Philipp Kuinke, Fernando Sánchez Villaamil, Markus L. Schmid, Erik Jan van Leeuwen |
---|---|
DOI: | https://doi.org/10.1016/j.dam.2018.08.011 |
ISSN: | 0166-218X |
ISSN: | 1872-6771 |
Titel des übergeordneten Werks (Englisch): | Discrete applied mathematics |
Verlag: | Elsevier |
Verlagsort: | Amsterdam [u.a.] |
Publikationstyp: | Wissenschaftlicher Artikel |
Sprache: | Englisch |
Datum der Erstveröffentlichung: | 26.10.2018 |
Erscheinungsjahr: | 2020 |
Datum der Freischaltung: | 14.12.2023 |
Freies Schlagwort / Tag: | Kernelization; algorithms; cliquy tree; exact algorithms; independency tree; parameterized complexity |
Band: | 272 |
Seitenanzahl: | 14 |
Erste Seite: | 2 |
Letzte Seite: | 15 |
Fördernde Institution: | DFG German Research Foundation (DFG)European Commission [FE 560/6-1] |
Organisationseinheiten: | Digital Engineering Fakultät / Hasso-Plattner-Institut für Digital Engineering GmbH |
DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke |
Peer Review: | Referiert |
Publikationsweg: | Open Access / Bronze Open-Access |