A cκn 5-Approximation algorithm for treewidth
Publication date
2016
Authors
Bodlaender, Hans
Drange, Pål GrØnås
Dregi, Markus S.
Fomin, Fedor V.
Lokshtanov, Daniel
Pilipczuk, MichaŁ
Editors
Advisors
Supervisors
Document Type
Article
Metadata
Show full item recordCollections
License
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.
Keywords
Algorithms, Approximation, Fixed parameter tractability, Graphs, Treewidth, General Mathematics, General Computer Science
Citation
Bodlaender, H L, Drange, P G, Dregi, M S, Fomin, F V, Lokshtanov, D & Pilipczuk, M 2016, 'A c κ n 5-Approximation algorithm for treewidth', SIAM Journal on Computing, vol. 45, no. 2, pp. 317-378. https://doi.org/10.1137/130947374