(2022) Domination and Cut Problems on Chordal Graphs with Bounded Leafage.
|
Text
IPEC-Domination_and_Cut.pdf - Submitted Version Download (925kB) | Preview |
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 \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.
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Divisions: | Dániel Marx (DM) |
| Conference: | IPEC International Symposium on Parameterized and Exact Computation (was IWPEC pre 2004) |
| Depositing User: | Philipp Schepper |
| Date Deposited: | 13 Oct 2022 09:17 |
| Last Modified: | 13 Oct 2022 09:17 |
| Primary Research Area: | NRA1: Trustworthy Information Processing |
| URI: | https://publications.cispa.saarland/id/eprint/3837 |
Actions
Actions (login required)
 |
View Item |