Domination and cut problems on chordal graphs with bounded leafage

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 2 O(ℓ)· 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.

Schlagworte

Chordal graphs

Dominating set

FPT algorithms

Leafage

MultiCut with undeletable terminals

Multiway cut with undeletable terminals

DDC Class

004: Computer Sciences

Projekt(e)

Projekt DEAL

Publication version

publishedVersion

Lizenz

https://creativecommons.org/licenses/by/4.0/

Name

s00453-023-01196-y.pdf

Type

main article

Size

782.85 KB

Format

Adobe PDF

Options

Domination and cut problems on chordal graphs with bounded leafage