Constant-factor treewidth approximation

For the path A–B–C, use two overlapping groups: {A,B} and {B,C}, linked in a two-node tree. Each edge is contained in a group, and B stays present across the overlap. For any graph, can an efficient algorithm find such a tree of groups whose largest group is within one fixed factor of the smallest achievable?[1]

Can an algorithm efficiently find a tree of small overlapping groups for every graph, close to the best possible arrangement? For A–B–C, bags {A,B} and {B,C} linked by a tree edge cover both graph edges. The bags containing B are connected, and the largest bag has two vertices, so the width is one.

A valid tree decomposition of a finite simple undirected graph covers every vertex, contains both endpoints of each edge in some bag, and makes the bags containing each vertex a connected subtree. If its width is w, the required polynomial-time guarantee is

$$w+1\leq C\bigl(\mathrm{tw}(G)+1\bigr),$$

for one constant C independent of G. Treewidth $\mathrm{tw}(G)$ is the minimum width; the added ones compare largest bag sizes directly.[1]

Polynomial-time methods give ratios that still depend on the graph’s treewidth; other good ratios require time exponential in that parameter. Conditional hardness rules out a very close approximation, but leaves the question of a larger fixed factor.[1] [2]

Bonnet’s 2026 hardness excludes a sufficiently close ratio under P ≠ NP, not all constants. Stronger conjecture-based hardness remains conditional.[2]

Small overlapping groups let an algorithm work on graph pieces while remembering choices on the vertices they share. Agreement at the overlaps lets partial answers fit together. The group sizes control how much boundary information must be tracked. Finding a useful grouping therefore connects the graph’s structure to the information needed to combine local solutions, rather than assuming that organization is already available.[1]

A bag separates its branch of the decomposition from the rest of the graph. Recording partial solutions’ choices on that boundary lets different pieces be joined consistently. A bag of $w+1$ vertices has $2^{w+1}$ yes/no patterns before constraints are applied; connectivity problems may need additional records. Small bags therefore restrict the information passed between subproblems. Finding a good decomposition matters because methods that assume one is supplied inherit its boundary sizes, and an oversized bag can lose that structural advantage.[1]