TY - GEN
T1 - An FPT 2-approximation for tree-cut decomposition
AU - Kim, Eunjung
AU - Oum, Sang Il
AU - Paul, Christophe
AU - Sau, Ignasi
AU - Thilikos, Dimitrios M.
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - 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 2O(w2 log w) ・ 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.
AB - 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 2O(w2 log w) ・ 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.
KW - Approximation algorithm
KW - Fixed-parameter tractable algorithm
KW - Tree-cut width
UR - http://www.scopus.com/inward/record.url?scp=84956644549&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84956644549&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-28684-6_4
DO - 10.1007/978-3-319-28684-6_4
M3 - Conference contribution
AN - SCOPUS:84956644549
SN - 9783319286839
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 35
EP - 46
BT - Approximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers
A2 - Skutella, Martin
A2 - Sanità, Laura
PB - Springer Verlag
T2 - 13th International Workshop on Approximation and Online Algorithms, WAOA 2015
Y2 - 17 September 2015 through 18 September 2015
ER -