A Single-Exponential Time 2-Approximation Algorithm for Treewidth

2022/02/01 by Tuukka Korhonen · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory #Treewidth #Tree decomposition #Combinatorics #Vertex (graph theory) #Exponential function #Mathematics #Tree-depth #Graph #Integer (computer science) #Algorithm #Discrete mathematics #1-planar graph #Pathwidth #Computer science #Chordal graph #Line graph #Mathematical analysis

paper · doi:10.1109/focs52979.2021.00026

openalex publication_date 2022/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

We give an algorithm, that given an n-vertex graphGand an integer k, in time 2O(k)n either outputs a tree decomposition ofGof width at most 2k + 1 or determines that the treewidth ofGis 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 2O(k)n and the previous best approximation ratio of 3 in time 2O(k)nO(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].

Citations

• Linear time algorithms for NP-hard problems restricted to partial k-trees
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• The monadic second-order logic of graphs. I. Recognizable sets of finite graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Complexity of Finding Embeddings in a k-Tree
• Dynamic programming on graphs with bounded treewidth
• Finding approximate separators and computing tree width quickly
• A c^k n 5-Approximation Algorithm for Treewidth
• Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth

Cited by

• Treewidth [wikipedia]