Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2022.14
URN: urn:nbn:de:0030-drops-173704
URL: https://drops.dagstuhl.de/opus/volltexte/2022/17370/
Galby, Esther ; Marx, Dániel ; Schepper, Philipp ; Sharma, Roohani ; Tale, Prafullkumar
Domination and Cut Problems on Chordal Graphs with Bounded Leafage
| pdf-format: |
|
Abstract
The leafage of a chordal graph G is the minimum integer 𝓁 such that G can be realized as an intersection graph of subtrees of a tree with 𝓁 leaves. We consider structural parameterization by the leafage of classical domination and cut problems on chordal graphs. Fomin, Golovach, and Raymond [ESA 2018, Algorithmica 2020] proved, among other things, that Dominating Set on chordal graphs admits an algorithm running in time 2^𝒪(𝓁²) ⋅ n^𝒪(1). We present a conceptually much simpler algorithm that runs in time 2^𝒪(𝓁) ⋅ n^𝒪(1). We extend our approach to obtain similar results for Connected Dominating Set and Steiner Tree. We then consider the two classical cut problems MultiCut with Undeletable Terminals and Multiway Cut with Undeletable Terminals. We prove that the former is W[1]-hard when parameterized by the leafage and complement this result by presenting a simple n^𝒪(𝓁)-time algorithm. To our surprise, we find that Multiway Cut with Undeletable Terminals on chordal graphs can be solved, in contrast, in n^O(1)-time.
BibTeX - Entry
@InProceedings{galby_et_al:LIPIcs.IPEC.2022.14,
author = {Galby, Esther and Marx, D\'{a}niel and Schepper, Philipp and Sharma, Roohani and Tale, Prafullkumar},
title = {{Domination and Cut Problems on Chordal Graphs with Bounded Leafage}},
booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
pages = {14:1--14:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-260-0},
ISSN = {1868-8969},
year = {2022},
volume = {249},
editor = {Dell, Holger and Nederlof, Jesper},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17370},
URN = {urn:nbn:de:0030-drops-173704},
doi = {10.4230/LIPIcs.IPEC.2022.14},
annote = {Keywords: Chordal Graphs, Leafage, FPT Algorithms, Dominating Set, MultiCut with Undeletable Terminals, Multiway Cut with Undeletable Terminals}
}
| Keywords: | Chordal Graphs, Leafage, FPT Algorithms, Dominating Set, MultiCut with Undeletable Terminals, Multiway Cut with Undeletable Terminals | |
| Seminar: | 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 14.12.2022 |
