Options
Domination and cut problems on chordal graphs with bounded leafage
Citation Link: https://doi.org/10.15480/882.4872
Publikationstyp
Conference Paper
Date Issued
2022-09
Sprache
English
Institut
TORE-DOI
First published in
Number in series
249
Article Number
14
Citation
International Symposium on Parameterized and Exact Computation (IPEC 2022)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH
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 2O(ℓ2) · nO(1). We present a conceptually much simpler algorithm that runs in time 2O(ℓ)·nO(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 nO(ℓ)-time algorithm. To our surprise, we find that Multiway Cut with Undeletable Terminals on chordal graphs can be solved, in contrast, in nO(1)-time.
Subjects
Chordal Graphs
Dominating Set
FPT Algorithms
Leafage
MultiCut with Undeletable Terminals
Multiway Cut with Undeletable Terminals
DDC Class
004: Informatik
Publication version
publishedVersion
Loading...
Name
2208.02850.pdf
Size
547.46 KB
Format
Adobe PDF