A Single-Exponential Time 2-Approximation Algorithm for Treewidth

We give an algorithm, that given an n-vertex graph $G$ and an integer k, in time 2 O(k) n either outputs a tree decomposition of $G$ of width at most 2k + 1 or determines that the treewidth of $G$ is larger than k. This is the first 2-approximation algorithm for treewidth that is faster than the known exact algorithms. In particular, our algorithm improves upon both the previous best approximation ratio of 5 in time 2 O(k) n and the previous best approximation ratio of 3 in time 2 O(k) n O(1), both given by Bodlaender et al. [FOCS 2013, SICOMP 2016]. Our algorithm is based on a local improvement method adapted from a proof of Bellenbaum and Diestel [Comb. Probab. Comput. 2002].

Authors

• Tuukka Korhonen

Keywords

• Computer science
• Upper bound
• Heuristic algorithms
• Approximation algorithms
• Dynamic programming
• Time complexity
• Treewidth
• 2-approximation Algorithm
• Approximate Ratio
• Exact Algorithm
• Joining Tree
• Data Structure
• Running Time
• Source Code
• Estimation Algorithm
• Internal State
• Root Node
• Subtree
• Maximum Degree
• Query Set
• Depth-first
• Table Entries
• Operator Splitting
• Total Time Complexity
• Empty Bag
• FPT-approximation