An FPT 2-Approximation for Tree-Cut Decomposition

Cited 1 time in webofscience Cited 0 time in scopus
  • Hit : 181
  • Download : 0
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 2 O(w 2 logw) ⋅n 2 2O(w2log⁡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.
Publisher
SPRINGER
Issue Date
2018-01
Language
English
Article Type
Article
Keywords

LINEAR-TIME; GRAPH MINORS; ALGORITHMS; TREEWIDTH; WIDTH

Citation

ALGORITHMICA, v.80, no.1, pp.116 - 135

ISSN
0178-4617
DOI
10.1007/s00453-016-0245-5
URI
http://hdl.handle.net/10203/239463
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 1 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0