A Single-Exponential Time 2-Approximation Algorithm for Treewidth

1 Introduction

• Treewidth approximations support 2^O(k)n algorithms for many classically hard graph problems, and lowering the width factor speeds those algorithms [Cou90, AP89, Bod88, BCKN15].Before this work, the 5-approximation was the only constant-factor approximation with running time 2^O(k)n; a 3-approximation required 2^O(k)n log n [BDD+16].Source: §1 · pp. 2–3
• In time 2^O(k)n, the algorithm outputs a tree decomposition of width at most 2k + 1 or determines that the treewidth exceeds k.This is a 2-approximation improving the previous ratio of 5 achieved in time 2^O(k)n.Source: §1 · pp. 2–3
• Unlike earlier approximation algorithms, which build decompositions top-down using balanced separators, this approach makes local improvements [RS95, Ami10, BF21, BDD+16, BGHK95, FHL08, FLS+18, Lag96, Ree92].The paper describes this as the first treewidth algorithm to apply Bellenbaum and Diestel’s technique in this setting.Source: §1 · p. 3
• The algorithm iteratively improves a tree decomposition, extending Bellenbaum and Diestel’s technique so improvement remains possible while its width exceeds 2k + 1.Bags larger than 2k + 2 are splittable; the resulting operation does not increase width and reduces the number of largest-size bags.Source: §1 · pp. 3–4
• Local edits and dynamic programming over the changing decomposition reduce the total work to 2^O(k)n, with states recomputed only for edited bags.A walk maintains dynamic-programming tables directed toward the current node and handles each improvement locally around its splittable bag.Source: §1 · p. 4
• The algorithm assumes an initial decomposition of width O(k), available through Bodlaender’s compression technique with a k^O(1) time overhead.In this algorithm, the assumed input decomposition has width at most 4k + 3.Source: §1 · p. 4

2.1 Notation

• The notation distinguishes graph vertices and edges from tree-decomposition nodes and defines rooted-tree relations such as ancestor, descendant, and parent.It also defines neighborhoods, induced subgraphs, paths, and separation of vertex sets.Source: §2.1 · pp. 4–5

2.2 Tree decompositions

• A tree decomposition assigns bags to tree nodes, covers every graph vertex and edge, and places the bags containing each vertex on a connected subtree.Its width is the maximum bag size minus one; in a graph of treewidth k, any vertex set has a balanced separator of size at most k + 1.Source: §2.2 · p. 5

2.3 Bodlaender’s compression technique

• Compression reduces the task to improving a supplied decomposition from width 4k + 3 to width 2k + 1, or determining treewidth exceeds k.It contracts a large matching, recurses on the smaller graph, then expands bags; the recursion yields an overall k^O(1)n overhead beyond the improvement algorithm.Source: §2.3 · p. 6

3.1 Splittable vertex sets

• In a graph of treewidth at most k, every vertex set of size at least 2k + 3 is splittable.A split partitions vertices into three pairwise nonadjacent parts and a separator X, with each part's intersection with W together with X smaller than W.Source: §3.1 · pp. 6–7
• A minimum split first minimizes |X|, then minimizes the total distance from vertices in X's home bags to the root.This tie-breaking choice underpins the lemma that bounds the sizes of replacement bags.Source: §3.1 · p. 7

3.2 The improvement operation

• The operation builds decompositions for each G[C_i ∪ X], then joins their root bags to a new bag X.Vertices in X are inserted along root-to-home-bag paths to maintain connectedness; the resulting structure is a tree decomposition of G.Source: §3.2 · pp. 7–8
• For each bag B and distinct i, j, either |B^X| is less than |B ∩ (C_i ∪ C_j)| or B^X is empty.This structural property is used to prove that the operation does not increase bag sizes.Source: §3.2 · p. 9
• Each replacement keeps bag sizes no larger and strictly reduces bags of the largest size when the root bag is largest.For a bag B, the replacement forms B_i from its part in C_i ∪ X and the inserted vertices B^X.Source: §3.2 · p. 9

4 Amortized local improvement

• A direct improvement operation can cost Ω(n) and lead to Ω(n²) total time, while pruning limits each operation's edits to a subtree containing the root bag.The pruned version bounds the total number of edited bags over the algorithm by 2^O(k)n.Source: §4 · pp. 9–10

4.1 Pruned improvement operation

• Editable bags intersect at least two split parts and have editable ancestors; covered rooted subtrees are copied directly into the corresponding pruned decomposition.The construction connects the pruned decompositions to a new bag containing X, and the result remains a tree decomposition.Source: §4.1 · pp. 10–11
• The pruned operation preserves maximum degree 3 by duplicating a split-root bag when needed before connecting the pruned decompositions to X.A root bag with three children is split into two copies so its degree remains at most 3.Source: §4.1 · p. 12

4.2 Amortization

• Each operation on a largest bag decreases the w-potential by at least its number of editable bags, bounding the total editable bags by 2^O(w)n.The potential begins bounded by O(3^k k |V(T)|) for a decomposition of width k.Source: §4.2 · pp. 12–13

• The pruned improvement operation is implemented in 2^O(k)t time, where t is the number of editable bags.Walking the decomposition to apply the operation to all largest bags takes 2^O(k)n total time.Source: §5 · p. 13

• Given a degree-3 decomposition of width w with 2k + 2 ≤ w ≤ 4k + 3, the algorithm outputs one of width at most w − 1 or concludes treewidth exceeds k.O(k) applications yield the algorithm of Theorem 1.1, up to a k^O(1) time factor.Source: §5.1 · p. 14
• A width-w decomposition can be converted to one of maximum degree 3, width w, and O(n) bags in w^O(1)(n+|T|) time.The algorithm assumes its input has this form.Source: §5.1 · p. 14
• The data structure maintains a root pointer and supports initialization, movement, split detection, state retrieval, and subtree replacement.The stated operation costs are 2^O(w)n for initialization, 2^O(w) for movement and split, and 2^O(w)(|T1|+|T2|) for an edit.Source: §5.1 · p. 14

5.2 The data structure

• The dynamic program is directed toward the root; moving the root or editing the decomposition requires recomputing tables only for affected nodes or inserted subtrees.State queries trace a stored solution backward, while edits rebuild tables bottom-up.Source: §5.2 · p. 14

5.2.1 Stored information

• Each table entry records whether a subtree admits a partition consistent with the bag and, if so, the minimum boundary size h and an associated distance measure.At the root, the distance measure breaks ties after minimizing |X|.Source: §5.2.1 · p. 15

5.2.2 Transitions

• Transitions combine child tables through introduce, forget, and join steps, with each node's entries computable in 2^O(w) time.The decomposition into these standard transitions uses O(w) steps.Source: §5.2.2 · p. 15

5.2.3 Split query

• A Split query searches bag partitions and boundary sizes satisfying the split inequalities, selecting a valid entry that first minimizes h and then the stored distance.It returns failure if no such entry is valid.Source: §5.2.3 · p. 16

5.2.4 Move query

• A Move query transfers the root to an adjacent node by recomputing only the two endpoint tables, taking 2^O(w) time.It first traces the successful split backward when child internal states are invalid.Source: §5.2.4 · pp. 16–17

5.2.5 Init query

• Initialization computes the dynamic-programming tables bottom-up in 2^O(w)n time for a decomposition with O(n) nodes.Source: §5.2.5 · p. 17

5.2.6 State query

• A State query returns the partition of the current root bag specified by its stored internal state.Source: §5.2.6 · p. 17

5.2.7 Edit query

• An Edit query builds tables for the inserted subtree bottom-up, then moves the root to its specified node; its total cost is 2^O(w)|T2| + w^O(1)|T1|.Source: §5.2.7 · p. 17

5.3 The algorithm

• A split query finds a minimum split; traversal queries locate editable bags and their partitions, then the algorithm computes the needed sets bottom-up and constructs the replacement subtree.The replacement is the pruned improved tree decomposition for the editable bags.Source: §5.3 · pp. 17–18
• Depth-first Move operations traverse the decomposition, applying a pruned improvement at each visited bag of size w + 1 and treating new nodes as unseen.If such a bag is not splittable, the procedure returns that treewidth exceeds k.Source: §5.3 · p. 18
• The traversal maintains open nodes as a path and open plus unseen nodes as a subtree, supporting its correctness despite subtree replacements.The path runs from the added empty-bag node h to the current root pointer.Source: §5.3 · p. 19
• 2^O(w)n time suffices to reduce a degree-3 decomposition’s width from w to at most w − 1, or determine treewidth exceeds k, when 2k + 2 ≤ w ≤ 4k + 3.This is the per-round guarantee for the algorithm in this section.Source: §5.3 · p. 19
• 2^O(w)n bounds the total running time: editable bags are bounded over the algorithm, and Move operations advance nodes from unseen to open or open to closed.The total number of editable bags is at most ϕw(T) = 2^O(w)n.Source: §5.3 · p. 19

5.4 Analysis of the 2O(k) factor

• For w ≥ 3k + 3, restricting to two-way splits reduces the per-bag partition count from O(4^w) to O(3^w).In this regime the split fixes C3 = ∅.Source: §5.4 · p. 20
• O(2^10.8k n) is the overall running-time bound; the analysis gives O(2^10.4k n) when w ≥ 3k + 3 and O(2^10.8k n) when w < 3k + 3.Polynomial factors in k are absorbed into the exponential bound.Source: §5.4 · p. 20

6 Conclusion

• A 2-approximation in 2^O(k)n improves the best ratio at that running time from 5 to 2 and is faster than known exact algorithms.Source: §6 · p. 20
• Finding a constant-factor approximation with running time c^k n for small c remains open, despite progress on the hidden k-dependence.The authors describe their worst-case bounds as somewhat impractical, while suggesting the techniques may suit practical implementations.Source: §6 · p. 20
• Later work extended the techniques to rankwidth approximation, exact treewidth algorithms, and dynamic maintenance of small-width decompositions.These developments followed the conference version [Kor21].Source: §6 · p. 21