---
abstract: '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 <span style="font-variant:small-caps;">Dominating Set</span> 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 <span style="font-variant:small-caps;">Connected Dominating Set</span> and <span style="font-variant:small-caps;">Steiner Tree</span>. We then consider the two classical cut problems <span style="font-variant:small-caps;">MultiCut with Undeletable Terminals</span> and <span style="font-variant:small-caps;">Multiway Cut with Undeletable Terminals</span>. We prove that the former is \[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 <span style="font-variant:small-caps;">Multiway Cut with Undeletable Terminals</span> on chordal graphs can be solved, in contrast, in $n^{\calO(1)}$-time.'
author:
- Esther Galby
- Dániel Marx
- Philipp Schepper
- Roohani Sharma
- Prafullkumar Tale
bibliography:
- 'references.bib'
title: Domination and Cut Problems on Chordal Graphs with Bounded Leafage
---



{'source': 'arXiv_out/2208'}