An O(c^k n) 5-Approximation Algorithm for Treewidth

We give an algorithm that for an input n-vertex graph G and integer k > 0, in time O(c k n) either outputs that the tree width of G is larger than k, or gives a tree decomposition of G of width at most 5k + 4. This is the first algorithm providing a constant factor approximation for tree width which runs in time single-exponential in k and linear in n. Tree width 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 tree width and linear in the input size.

Authors

• Hans L. Bodlaender
• Pål Grønås Drange
• Markus S. Dregi
• Fedor V. Fomin
• Daniel Lokshtanov
• Michal Pilipczuk

Keywords

• Approximation algorithms
• Heuristic algorithms
• Approximation methods
• Dynamic programming
• Particle separators
• Partitioning algorithms
• Polynomials
• Constant Factor
• Joining Tree
• Constant Approximation
• Data Structure
• Running Time
• Cardinality
• Black Box
• State Structures
• Estimation Algorithm
• Steps Of Algorithm
• Linear Time
• Dynamic Algorithm
• Tree Depth
• Recursive Algorithm
• Approximate Ratio
• Dynamic Programming Algorithm
• Compression Algorithm
• Query Time
• Induced Subgraph
• Linear-time Algorithm
• Recursive Step
• Compression Step
• Time Constant
• First Search
• State Machine
• Total Run Time
• Automata
• Linear Algorithm
• treewidth
• fixed-parameter tractability
• approximation