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
O(ℓ
2)
· n
O(1). We present a conceptually much
simpler algorithm that runs in time 2
O(ℓ)
·n
O(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
O(ℓ)
-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.