Optimized 2-Approximation of Treewidth

Mahdi Belbasi; Martin F\"urer; Medha Kumar

REVIEW 3 major objections 6 minor 11 references

Optimized 2-Approximation of Treewidth

T0 review · 3 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper gives an FPT algorithm that, in $O^*(81^k)n$ time, produces a tree decomposition of width at most $2k+1$ or certifies that the treewidth exceeds $k$, improving the previous exponential base from 1782 to 81.

desk verdict The grouped tree decomposition is a real idea, but the stated 81^k bound rests on a 3-partition table that the paper never defines; as written the proof supports 256^k, which is still a big improvement over Korhonen. read the letter →

arxiv 2411.16918 v3 pith:D433GF43 submitted 2024-11-25 cs.DS

Mahdi Belbasi , Martin Fürer , Medha Kumar This is my paper · ORCID

classification cs.DS MSC 05C8568Q2568R10

keywords fixed-parametertractabilitytreewidthtreedecomposition2-approximationlinear-timealgorithmdynamicprogrammingpotentialfunctiongraphalgorithms

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper presents an algorithm that takes a graph together with a tree decomposition of width at most $4k+3$ and, in time $O^*(81^k)n$, either produces a tree decomposition of width at most $2k+1$ or correctly concludes that the treewidth is greater than $k$. Combined with a standard reduction, this yields a linear-time fixed-parameter 2-approximation of treewidth. The exponential base 81 drops from 1782 for the same task. The improvement comes from a specially structured 'grouped tree decomposition' that permits merging redundant nodes, and from the claim that in the high-width phase a three-way split with smaller DP tables suffices.

What carries the argument

The central object is the grouped tree decomposition: a rooted tree decomposition whose nodes alternate between main nodes and intersection nodes, where every non-root main node is the home of exactly one vertex, intersection nodes are subsets of their parent's bag, and each main node has at most $2^{|B|}-1$ children. This structure allows redundant main nodes to be merged into their grandparent, keeping the decomposition small enough for a linear-time analysis. The argument is carried by dynamic programming tables over partitions of each bag (initially 4-partitions, size $4^{|B|}$), a top-down Split operation that edits all editable nodes, and a potential function $\phi = \alpha+\beta+\gamma+\delta$ that amortizes the cost of DP-table recomputations during moves, splits, and merges. The claimed speed-up to $81^k$ relies on Remark 24, which asserts that in the high-width range $[3k+3, 4k+3]$ a 3-partition split with tables of size $3^{|B|}$ suffices, although the paper only specifies the 4-partition update rules.

What would settle it

Implement Algorithm 1 using exactly the four-partition DP tables defined in Section 2.2 on a graph with treewidth $k$ and an initial decomposition of width $4k+3$. If the algorithm fails to find a split at some node in the high-width range, or requires separator size greater than $k+1$, then Remark 24's 3-partition claim is false. Alternatively, construct any graph whose unique minimum-size good partition at a root bag of size $3k+3$ has four non-empty parts; such a graph would be a counterexample to the 3-partition split.

Watch

Extended reading notes

Core claim

The central claim is that the split-and-recompute scheme of the previous 2-approximation algorithm can be reorganized so that the dynamic programming tables used to find good splits are over three parts instead of four during the width range $[3k+3, 4k+3]$, shrinking the table size from $4^{|B|}$ to $3^{|B|}$ and giving the $O^*(81^k)n$ bound. The algorithm maintains a grouped tree decomposition, a rooted decomposition with alternating main and intersection nodes and the unique-home property, which lets it merge redundant nodes and keeps the number of node copies bounded. The proof shows that a potential function $\phi = \alpha+\beta+\gamma+\delta$ bounds the number of DP-table recomputations per round, and that each round decreases the maximum bag size. The paper concludes that the algorithm yields a 2-approximation of treewidth in linear time $O^*(81^k)n$, improving the previous $O^*(1782^k)n$.

Load-bearing premise

The $81^k$ bound rests on the unproven assertion (Remark 24) that a three-way split with $3^{|B|}$-sized tables works for widths $3k+3$ to $4k+3$; the paper only defines four-way split tables, so if the assertion fails the running time is $O^*(256^k)n$.

Editorial extensions

If this is right

Corollary 2 removes the need for an input decomposition: the algorithm itself, in $O^*(81^k)n$, either returns a tree decomposition of width at most $2k+1$ or proves $tw(G) > k$.
The running time is linear in $n$, so for any fixed $k$ the algorithm scales to large graphs.
Compared with the previous 2-approximation, the exponential base drops from 1782 to 81, so the same time budget covers values of $k$ that are larger by a factor of about $\log_{81} 1782 \approx 1.70$.
The analysis identifies the width range $[3k+3, 4k+3]$ as the bottleneck; improvements there would directly lower the exponential base further.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Our inference: even if Remark 24's 3-partition claim fails, the algorithm with the defined 4-partition tables runs in $O^*(256^k)n$, which still improves on the previous $1782^k$ bound; thus the grouped-decomposition optimization carries value independently.
Our inference: the grouped tree decomposition's ability to merge redundant nodes addresses a structural constraint that also limits branchwidth approximation; adapting this idea could yield faster FPT approximations of branchwidth.
Our inference: the 3-partition claim could be tested experimentally by instrumenting Algorithm 1 in the high-width range to count how often a good split requires four non-empty parts; such an experiment would also guide a rigorous proof or counterexample for Remark 24.
Our inference: if the 3-partition split is validated, a natural generalization is an $m$-partition split with DP-table base $m+1$ for intermediate width ranges, potentially yielding a trade-off curve between approximation quality and exponential base.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The main new thing here is the grouped tree decomposition (Def 6) and the merge operation that lets you collapse redundant nodes. That is a genuine structural departure from Korhonen's copy-heavy split, and it is what makes the claimed speedup plausible. The paper also gives a mostly careful account of the DP tables and the potential function, and it is honest about where the constants interact. The linear-in-n part and the overall high-level strategy look right to me.

The soft spot is the one you flagged, and I think it is real. The only data structure actually defined is the 4-partition DP table in Section 2.2, and every operation in Section 3.1 is specified over four parts. Then Remark 24 asserts that in the range b in [3k+4, 4k+4] it suffices to use a 3-partition split, so tables are size 3^{4k} = O(81^k). But there is no 3-partition table defined, no update rules for it, and no argument that the Split/Merge machinery still works if you only track three components. That switch is load-bearing: it is exactly the difference between 81^k and 256^k. If the switch fails, Theorem 25 proves only O*(256^k)n — still an improvement over Korhonen's 1728^k, but not the advertised result.

Some other lemmas are sketchier than they should be. Lemma 12 hand-waves through the separator-to-split step, Lemma 16's virtual-node potential argument is hard to follow, and Theorem 22's constants are asserted as "appropriate" without checking the inequalities. None of this looks fatal; it is the kind of thing a careful revision can fix. There is also a minor typo: the abstract says 1782^k where the body says 1728^k.

Who gets value from this: anyone working on FPT treewidth approximation. The structural idea is worth serious attention even if the current writeup does not fully prove the headline bound. I would send it to peer review and ask for a revision that either specifies the 3-partition tables or explicitly downgrades the main theorem to 256^k. I would not desk-reject it.

Referee Report

3 major / 6 minor

Summary. The paper presents an FPT 2-approximation algorithm for treewidth running in time O*(81^k)n, improving on Korhonen's earlier O*(1728^k)n bound. The algorithm takes as input a tree decomposition of width at most 4k+3, converts it into a grouped tree decomposition with a unique-home property, and then repeatedly splits nodes whose bags have maximum size, using DP tables over four-part partitions to find and propagate splits. The analysis uses a potential function φ(T)=α+β+γ+δ to bound the number of DP-table updates per round, and arrives at the claimed O*(81^k)n bound. The main claimed contribution is the improved exponential base, obtained by using four-part splits only when bag sizes are in the lower range and 3-partition splits in the higher range.

Significance. If the central claim holds, the paper is significant: it improves the exponential base for a linear-time 2-approximation of treewidth from 1728^k to 81^k, a notable step in a line of work that has focused on reducing the dependence on k. The grouped tree decomposition and the potential-function framework are reasonable and the paper contains a substantial amount of algorithmic detail, including pseudocode and lemmas for the main operations. However, the claimed improvement over Korhonen's algorithm is entirely contained in the O*(81^k) bound, and that bound rests on a compression of the DP tables that is asserted but not proven. The manuscript is honest about the structure of the algorithm and does not appear to be fitted to the target running time in a circular way, but the incomplete proof of the key constant prevents the paper from being accepted as written.

major comments (3)

[Remark 24 and Theorem 25] The O*(81^k) running time depends on the claim in Remark 24 that, when the maximum bag size b is in [3k+4, 4k+4], it suffices to create a 3-partition split, giving DP-tables of size 3^{4k}=O(81^k). However, the data structure defined in Section 2.2 stores a DP-table A_x of size 4^{|B_x|} for every 4-partition of B_x, and every operation in Section 3.1 (Initialization, Addition in both cases, Subtraction, Update) is specified for the four-part partition (W_1,W_2,W_3,X). No 3-partition table is defined, no update rules for it are given, and no argument is supplied that a 3-partition split can be found or maintained using only 3^{|B_x|} states while preserving the Split and Merge procedures of Algorithms 5 and 6. If the full 4-partition table is retained in the high-width range, the cost is 4^{4k+3}=O(256^k), not O(81^k). Since the claimed improvement over Korhonen's 1728^k is precisely the base 81 versus 256, this gap is load-bearing for Corollary 2.
[Lemma 12] The proof of split existence is not rigorous. The argument that a violation of property (a) at node y can be fixed by 'moving all vertices of C_i ∩ V_y from C_i to a C_j with j∈a(x)' does not check that the resulting partition remains legal, remains compatible with the partitions already chosen at ancestors, or preserves the minimality condition in Definition 10. Similarly, the treatment of a violation of property (b) says that 'there is a better partition P′ which differs from P only in V_y, is of the same minimal size, and has a larger intersection with B_y', but the definitions of good partitions and splits do not by themselves imply the existence of such a P′; this is essentially the central combinatorial claim that a good partition can be extended to a split. Since Algorithm 1 assumes a split exists in every round when the root bag is larger than 2(k+1), Lemma 12 needs a detailed proof, not a sketch.
[Lemma 16 and Theorem 22] The potential argument that α(T) is invariant under Move and that α and δ pay for Splits is stated with informal bookkeeping. In Lemma 16, the virtual-node chain is described verbally, and the proof asserts that 'the α potential given to node r_{ℓ+1} is the same as the α potential of x' and that the potential of removed virtual nodes 'is exactly the same' as the potential of added main nodes, but no explicit formula is given for f(x)=|B_x\B_{p(x)}| (or (|B_x|+1)/2 at the root) after rotations, merges, and the creation of up to O(k) intermediate nodes. Theorem 22 similarly asserts that the decrease in α pays for updating all copies and intersection parents without a term-by-term inequality. These arguments are load-bearing because Theorem 23 concludes that φ(T) bounds the number of table updates per round. Please provide a formal accounting of the potential changes in Rotate, Merge, and Split, or state clearly which inequalities among c_α,c_β,c_γ,c_δ are required and prove that they can be satisfied.

minor comments (6)

[Abstract and Section 4] The abstract states Korhonen's running time as O(poly(k)1782^k n), while Section 4 and the stated bound use 1728^k; the inconsistent constant should be corrected.
[Lemma 5] The proof of Lemma 5 ends with two QED symbols; remove the duplicate.
[Definition 10] The sentence 'Note that at least two sets W_i^r are non-empty for the root r' is asserted without proof and is not immediate from the definition of a good partition; either prove it or soften the claim.
[Lemma 18] Lemma 18 states that the number of rotations is at most a constant factor times the number of DFS steps, but no constant is identified and the argument is only one sentence. Since Move is implemented as a series of rotations, the statement should either be given a proof or the factor should be made explicit to ensure it is independent of k.
[Theorem 25] The proof says the potential gives 'a geometrically decreasing potential function' across rounds, but no explicit series or ratio is shown. Since the number of rounds is O(k), the claimed total O(k^2 81^k n) should be justified with a concrete bound on the sum of potentials over rounds.
[Algorithms 5 and 6] There are small formatting issues, such as 'Fora(x) ={i}' in Algorithm 6, and Algorithm 5 refers to 'Add y to x' where the parent relationship is unclear. These should be cleaned up for readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the 2-approximation algorithm is derived from explicit DP-table recurrences and potential-function analysis, not from its own conclusion.

full rationale

The paper's central derivation is self-contained in the sense required by the circularity test: Theorem 25 and Corollary 2 follow from the DP-table definitions in Section 2.2, the node operations in Section 3.1, and the potential-function accounting in Theorem 23 and Remark 24. The DP tables store sizes of legal 4-partitions, and the Addition, Subtraction, and Update rules are explicit recurrences over those tables; the claimed running time is obtained by bounding table sizes and the number of table recomputations via alpha, beta, gamma, and delta potentials. No parameter is fitted to the target output, and no quantity that the paper claims to predict is used as an input to its own derivation. The self-citations [2,3] of Belbasi and Fuerer are cited in the introduction as prior work on reducing exponential coefficients in treewidth approximation; they are not used to justify any load-bearing uniqueness claim or to define the algorithm's correctness. The only notable concern in the paper is the non-circular correctness gap noted in Remark 24: the jump from 4-partition tables of size O(4^{4k}) to 3-partition tables of size O(3^{4k}) in the high-width range [3k+4, 4k+4] is asserted with a reference to Korhonen [8] but no explicit 3-partition table update rules are given. That is a missing proof or specification issue, not a circular reduction: the claim does not assume the 81^k bound as an input. Since the derivation is independent of its own conclusion and no fitted input is renamed as a prediction, the circularity score is 0.

Assumptions & free parameters 4 free parameters · 2 assumptions · 0 invented entities

The algorithm depends on standard separator theory (Robertson-Seymour), the ability to start from a 4-approximate tree decomposition, and the correctness of the grouped-tree-decomposition machinery developed in the paper. The potential-function constants are proof-construction constants satisfying inequalities in Remark 24; they are not fitted to data and do not affect the asymptotic claim. No invented entities are introduced.

free parameters (4)

c_alpha
Universal constant in the alpha potential term, required to satisfy c_alpha > max(c_beta, c_gamma, c_delta) in Remark 24. Not fitted to data; existence of a suitable constant is sufficient for the asymptotic bound.
c_beta
Constant in the beta potential term accounting for DFS-Status; chosen to satisfy the inequalities in Remark 24. Specific value does not affect the O*(81^k) claim.
c_gamma
Constant in the gamma potential term accounting for node count; chosen to satisfy the inequalities in Remark 24. Specific value does not affect the asymptotic claim.
c_delta
Constant in the delta potential term for maximum-size bags; must be large enough to cover new root and forget nodes, per Remark 24. Not data-fitted.

assumptions (2)

standard math Robertson-Seymour Lemma II.2: a graph of treewidth <= k has a balanced separator of size <= k+1 that splits B_r into components each containing at most half of B_r.
Used in Lemma 12 to establish the existence of a split when |B_r| > 2(k+1).
domain assumption Bodlaender's reduction method can supply an initial 4-approximate tree decomposition in polynomial(k) time, as used in Corollary 2.
The paper cites this as 'as in [8]' but does not prove it; it is load-bearing for the unconditional Corollary 2.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Optimized 2-Approximation of Treewidth." pith.science (2026). https://pith.science/paper/D433GF43

@misc{pith2026241116918,
  author       = {Pith},
  title        = {Pith review of: Optimized 2-Approximation of Treewidth},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/D433GF43}},
  note         = {Machine review of arXiv:2411.16918}
}

abstract

This paper presents a linear FPT algorithm to find a tree decomposition with a 2-approximation of the treewidth with a significantly smaller exponential dependence on the treewidth. The algorithm runs in time $O(\text{poly}(k) 81^k n)$, compared to Korhonen's running time of $O(\text{poly}(k) 1782^k n)$ = $O(2^{10.8k} n)$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 6 canonical work pages

[1]

Complexity of finding embeddings in a k -tree

Stefan Arnborg, Derek G Corneil, and Andrzej Proskurowski. Complexity of finding embeddings in a k -tree. SIAM Journal on Algebraic Discrete Methods , 8(2):277--284, 1987

work page 1987
[2]

Finding all leftmost separators of size k

Mahdi Belbasi and Martin F \" u rer. Finding all leftmost separators of size k . In Combinatorial Optimization and Applications - 15th International Conference, COCOA 2021 , LNCS 13135, pages 273--287. Springer, 2021. https://doi.org/10.1007/978-3-030-92681-6\_23 doi:10.1007/978-3-030-92681-6\_23

work page doi:10.1007/978-3-030-92681-6 2021
[3]

An improvement of R eed's treewidth approximation

Mahdi Belbasi and Martin F \" u rer. An improvement of R eed's treewidth approximation. J. Graph Algorithms Appl. , 26(2):257--282, 2022. https://doi.org/10.7155/jgaa.00593 doi:10.7155/jgaa.00593

work page doi:10.7155/jgaa.00593 2022
[4]

A linear-time algorithm for finding tree-decompositions of small treewidth

Hans L Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on computing , 25(6):1305--1317, 1996

work page 1996
[5]

A c^k n 5-approximation algorithm for treewidth

Hans L Bodlaender, P l Grøn s Drange, Markus S Dregi, Fedor V Fomin, Daniel Lokshtanov, and Micha Pilipczuk. A c^k n 5-approximation algorithm for treewidth. SIAM Journal on Computing , 45(2):317--378, 2016

work page 2016
[6]

Fomin and Tuukka Korhonen

Fedor V. Fomin and Tuukka Korhonen. Fast FPT -approximation of branchwidth. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , STOC 2022, page 886–899, New York, NY, USA, 2022. Association for Computing Machinery. https://doi.org/10.1145/3519935.3519996 doi:10.1145/3519935.3519996

arXiv 2022
[7]

A single-exponential time 2-approximation algorithm for treewidth

Tuukka Korhonen. A single-exponential time 2-approximation algorithm for treewidth. SIAM Journal on Computing , 0(0):FOCS21--174--FOCS21--194, 0. https://doi.org/10.1137/22M147551X doi:10.1137/22M147551X

doi:10.1137/22m147551x
[8]

A single-exponential time 2-approximation algorithm for treewidth

Tuukka Korhonen. A single-exponential time 2-approximation algorithm for treewidth. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 184--192, 2021. https://doi.org/10.1109/FOCS52979.2021.00026 doi:10.1109/FOCS52979.2021.00026

arXiv 2021

Show all 11 references

[9]

An improved parameterized algorithm for treewidth

Tuukka Korhonen and Daniel Lokshtanov. An improved parameterized algorithm for treewidth. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , STOC 2023, page 528–541, New York, NY, USA, 2023. Association for Computing Machinery. https://doi.org/10.1145/356...

2023
[10]

Graph minors

Neil Robertson and Paul D Seymour. Graph minors. III . P lanar tree-width. Journal of Combinatorial Theory, Series B , 36(1):49--64, 1984

1984
[11]

Neil Robertson and Paul D. Seymour. Graph minors II . A lgorithmic aspects of tree-width. J. Algorithms , 7(3):309--322, 1986. URL: http://dx.doi.org/10.1016/0196-6774(86)90023-4, https://doi.org/10.1016/0196-6774(86)90023-4 doi:10.1016/0196-6774(86)90023-4

1986 doi

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Complexity of finding embeddings in a k -tree

Stefan Arnborg, Derek G Corneil, and Andrzej Proskurowski. Complexity of finding embeddings in a k -tree. SIAM Journal on Algebraic Discrete Methods , 8(2):277--284, 1987

work page 1987

[2] [2]

Finding all leftmost separators of size k

Mahdi Belbasi and Martin F \" u rer. Finding all leftmost separators of size k . In Combinatorial Optimization and Applications - 15th International Conference, COCOA 2021 , LNCS 13135, pages 273--287. Springer, 2021. https://doi.org/10.1007/978-3-030-92681-6\_23 doi:10.1007/978-3-030-92681-6\_23

work page doi:10.1007/978-3-030-92681-6 2021

[3] [3]

An improvement of R eed's treewidth approximation

Mahdi Belbasi and Martin F \" u rer. An improvement of R eed's treewidth approximation. J. Graph Algorithms Appl. , 26(2):257--282, 2022. https://doi.org/10.7155/jgaa.00593 doi:10.7155/jgaa.00593

work page doi:10.7155/jgaa.00593 2022

[4] [4]

A linear-time algorithm for finding tree-decompositions of small treewidth

Hans L Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on computing , 25(6):1305--1317, 1996

work page 1996

[5] [5]

A c^k n 5-approximation algorithm for treewidth

Hans L Bodlaender, P l Grøn s Drange, Markus S Dregi, Fedor V Fomin, Daniel Lokshtanov, and Micha Pilipczuk. A c^k n 5-approximation algorithm for treewidth. SIAM Journal on Computing , 45(2):317--378, 2016

work page 2016

[6] [6]

Fomin and Tuukka Korhonen

Fedor V. Fomin and Tuukka Korhonen. Fast FPT -approximation of branchwidth. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , STOC 2022, page 886–899, New York, NY, USA, 2022. Association for Computing Machinery. https://doi.org/10.1145/3519935.3519996 doi:10.1145/3519935.3519996

arXiv 2022

[7] [7]

A single-exponential time 2-approximation algorithm for treewidth

Tuukka Korhonen. A single-exponential time 2-approximation algorithm for treewidth. SIAM Journal on Computing , 0(0):FOCS21--174--FOCS21--194, 0. https://doi.org/10.1137/22M147551X doi:10.1137/22M147551X

doi:10.1137/22m147551x

[8] [8]

A single-exponential time 2-approximation algorithm for treewidth

Tuukka Korhonen. A single-exponential time 2-approximation algorithm for treewidth. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 184--192, 2021. https://doi.org/10.1109/FOCS52979.2021.00026 doi:10.1109/FOCS52979.2021.00026

arXiv 2021