An FPT 2-Approximation for Tree-Cut Decomposition

3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Résumé : The tree-cut width of a graph is a graph parameter defined by Wollan [J. Comb. Theory, Ser. B, 110:47-66, 2015] with the help of tree-cut decompositions. In certain cases, tree-cut width appears to be more adequate than treewidth as an invariant that, when bounded, can accelerate the resolution of intractable problems. While designing algorithms for problems with bounded tree-cut width, it is important to have a parametrically tractable way to compute the exact value of this parameter or, at least, some constant approximation of it. In this paper we give a parameterized 2-approximation algorithm for the computation of tree-cut width; for an input $n$-vertex graph $G$ and an integer $w$, our algorithm either confirms that the tree-cut width of $G$ is more than $w$ or returns a tree-cut decomposition of $G$ certifying that its tree-cut width is at most $2w$, in time $2^{O(w^2\log w)} \cdot n^2$. Prior to this work, no constructive parameterized algorithms, even approximated ones, existed for computing the tree-cut width of a graph. As a consequence of the Graph Minors series by Robertson and Seymour, only the existence of a decision algorithm was known.
Document type :
Reports
Domain :

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01225569
Contributor : Dimitrios Thilikos <>
Submitted on : Friday, November 6, 2015 - 12:14:03 PM
Last modification on : Wednesday, February 19, 2020 - 8:54:54 AM

Identifiers

• HAL Id : lirmm-01225569, version 1
• ARXIV : 1509.04880

Citation

Eunjung Kim, Sang-Il Oum, Christophe Paul, Ignasi Sau Valls, Dimitrios M. Thilikos. An FPT 2-Approximation for Tree-Cut Decomposition. [Research Report] LIRMM. 2015. ⟨lirmm-01225569⟩

Record views