Domination and Cut Problems on Chordal Graphs with Bounded Leafage

Zusammenfassung

The leafage of a chordal graph $G$ is the minimum integer $\ell$ such that $G$ can be realized as an intersection graph of subtrees of a tree with $\ell$ 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 \textsc{Dominating Set} on chordal graphs admits an algorithm running in time $2^{\mathcal{O}(\ell^2)} \cdot n^{\mathcal{O}(1)}$. We present a conceptually much simpler algorithm that runs in time $2^{\mathcal{O}(\ell)} \cdot n^{\mathcal{O}(1)}$. We extend our approach to obtain similar results for \textsc{Connected Dominating Set} and \textsc{Steiner Tree}. We then consider the two classical cut problems \textsc{MultiCut with Undeletable Terminals} and \textsc{Multiway Cut with Undeletable Terminals}. We prove that the former is \textsf{W}[1]-hard when parameterized by the leafage and complement this result by presenting a simple $n^{\mathcal{O}(\ell)}$-time algorithm. To our surprise, we find that \textsc{Multiway Cut with Undeletable Terminals} on chordal graphs can be solved, in contrast, in $n^{\mathcal{O}(1)}$-time.