A cκn 5-Approximation algorithm for treewidth

H.L. Bodlaender, P.G. Drange, M.S. Dregi, F.V. Fomin, D. Lokshtanov, M. Pilipczuk

Research output: Contribution to journalArticleAcademicpeer-review

113 Citations (Scopus)

Abstract

We give an algorithm that for an input n-vertex graph G and integer κ > 0, in time 2O(κ)n, either outputs that the treewidth of G is larger than κ, or gives a tree decomposition of G of width at most 5κ + 4. This is the first algorithm providing a constant factor approximation for treewidth which runs in time single exponential in κ and linear in n. Treewidth-based computations are subroutines of numerous algorithms. Our algorithm can be used to speed up many such algorithms to work in time which is single exponential in the treewidth and linear in the input size.

Original languageEnglish
Pages (from-to)317-378
Number of pages62
JournalSIAM Journal on Computing
Volume45
Issue number2
DOIs
Publication statusPublished - 2016

Keywords

  • Algorithms
  • Approximation
  • Fixed parameter tractability
  • Graphs
  • Treewidth

Fingerprint Dive into the research topics of 'A c<sup>κ</sup>n 5-Approximation algorithm for treewidth'. Together they form a unique fingerprint.

Cite this