An FPT 2-approximation for tree-cut decomposition

Eunjung Kim, Sang Il Oum, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationApproximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers
EditorsMartin Skutella, Laura Sanità
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783319286839
StatePublished - 2015
Event13th International Workshop on Approximation and Online Algorithms, WAOA 2015 - Patras, Greece
Duration: Sep 17 2015Sep 18 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference13th International Workshop on Approximation and Online Algorithms, WAOA 2015


  • Approximation algorithm
  • Fixed-parameter tractable algorithm
  • Tree-cut width

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'An FPT 2-approximation for tree-cut decomposition'. Together they form a unique fingerprint.

Cite this