An FPT 2-Approximation for Tree-Cut Decomposition
Kim, Eun Jung; Oum, Sang-il; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2018), An FPT 2-Approximation for Tree-Cut Decomposition, Algorithmica, 80, 1, p. 116-135. 10.1007/s00453-016-0245-5
Type
Article accepté pour publication ou publiéExternal document link
https://arxiv.org/abs/1509.04880v1Date
2018Journal name
AlgorithmicaVolume
80Number
1Publisher
Springer
Pages
116-135
Publication identifier
Metadata
Show full item recordAuthor(s)
Kim, Eun JungLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Oum, Sang-il
Department of Mathematical Sciences, KAIST
Paul, Christophe
Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier [LIRMM]
Sau Valls, Ignasi

Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier [LIRMM]
Thilikos, Dimitrios M.

Computer Technology Institute and Press "Diophantus"
Abstract (EN)
The tree-cut width of a graph is a graph parameter defined by Wollan (J Combin 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 2O(w2logw)⋅n2 . 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.Subjects / Keywords
Fixed-parameter tractable algorithm; Tree-cut width; Approximation algorithmRelated items
Showing items related by title and author.
-
Kim, Eun Jung; Oum, Sang-Il; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2015) Communication / Conférence
-
Kim, Eun Jung; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2017) Article accepté pour publication ou publié
-
Cohen, Nathann; Gonçalves, Daniel; Kim, Eun Jung; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2017) Article accepté pour publication ou publié
-
Kim, Eun Jung; Langer, Alexander; Paul, Christophe; Reidl, Felix; Rossmanith, Peter; Sau Valls, Ignasi (2016) Article accepté pour publication ou publié
-
Kim, Eun Jung; Langer, Alexander; Paul, Christophe; Reidl, Felix; Rossmanith, Peter; Sau Valls, Ignasi; Sikdar, Somnath (2013-07) Communication / Conférence