{"id":"80217f25-cc14-4cb8-bb6f-4cc1050ae94f","arxiv_id":"2411.16918","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A new FPT algorithm approximates treewidth within a factor of 2 in O(poly(k) 81^k n) time, improving the previous 1728^k bound.","lead":"The paper presents a faster algorithm for approximating treewidth, a measure of how tree-like a graph is. If correct, it finds a near-optimal tree decomposition in time growing as 81 raised to the treewidth, far better than the previous best of about 1728 raised to the treewidth.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The O*(81^k) bound depends on an unspecified switch to 3-partition DP tables in the high-width range [3k+3,4k+3]; without explicit update rules, the proven table size remains 4^{|B|}=O(256^k).","rationale":"I agree with the Pith Reader's weakest_assumption. The 3-partition/4-partition discrepancy is not a stylistic gap: it is the exact place where the exponential constant 81 enters. The paper has independent strengths: the grouped tree decomposition is a real structural idea, Lemma 7's conversion is plausible, and the potential-function accounting (Theorems 22–23) is coherent at the level of table updates. But Theorem 25's proof literally says the DP-table size 'should be' 3^{4k} in the high-width range, while Section 2.2 and all update rules define 4-partition tables. There is no section that specifies how the table is stored or updated in that range. Because O* notation suppresses only polynomial factors, the choice between 3^{|B|} and 4^{|B|} is an exponential, decisive difference. I do not see an inconsistency that makes the approach impossible; a 3-partition split is a special case of the defined 4-partition split with one empty part, so the likely repair is to add explicit compressed-table update rules and verify the potential function. But 'likely repairable' is exactly what CONDITIONAL means, so I would keep the reader's CONDITIONAL verdict. No change to the verdict is needed.","tokens_in":14493,"tokens_out":7078,"duration_ms":65020,"concrete_test":"Provide the missing 3-partition analogue: define A_x over all assignments of B_x to {C_1,C_2,S} and state the update equations for Addition Case 1 (a new bag vertex v has only 3 destinations), Addition Case 2, Subtraction, Update, and the top-down split selection in Algorithm 6. Then count the number of states scanned in a round with |B_r|=3k+4. If any operation requires the fourth component or scans all 4^{|B|} entries, replace 81^k by 256^k in Theorem 25 and recompute the conclusion; this single check determines whether the central constant is proved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 25 and Corollary 2) is time O*(81^k)n. The only justification for the 81^k base is Remark 24: for bags of size b in [3k+4,4k+4] it 'suffices to simply create a 3-partition split [8]', giving DP-tables of size 3^{4k}=O(81^k). But the data structure actually defined is Section 2.2's DP-table A_x over all 4-partitions of B_x (size 4^{|B_x|}), and every operation in Section 3.1 — Initialization, Addition (both cases), Subtraction, Update — is specified over the four parts (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 by scanning only 3^{|B|} states while preserving the power of the Split/Merge machinery (Algorithms 5–6). If the full 4-partition table is stored and updated in the high-width range, the cost is 4^{4k+3}=O(256^k), not O(81^k). Theorem 22/23's potential accounting also assumes the per-table cost 4^{|B|}; compressing to 3^{|B|} would require a separate accounting for the high-width rounds. This is load-bearing because the entire claimed improvement over Korhonen's 1728^k is the constant 81 versus 256; if Remark 24 fails, the theorem as written only proves O*(256^k)n (still an improvement over Korhonen, but not the stated result). The gap is likely repairable — a 3-partition split is a special case of the 4-partition definition with one empty component — but the repair is absent from the manuscript.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":14824,"tokens_out":3161,"duration_ms":31511,"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":[{"comment":"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.","section":"Remark 24 and Theorem 25"},{"comment":"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.","section":"Lemma 12"},{"comment":"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.","section":"Lemma 16 and Theorem 22"}],"minor_comments":[{"comment":"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.","section":"Abstract and Section 4"},{"comment":"The proof of Lemma 5 ends with two QED symbols; remove the duplicate.","section":"Lemma 5"},{"comment":"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.","section":"Definition 10"},{"comment":"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.","section":"Lemma 18"},{"comment":"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.","section":"Theorem 25"},{"comment":"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.","section":"Algorithms 5 and 6"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a serious attempt at improving the exponential base for treewidth 2-approximation, and the grouped tree decomposition seems like a promising technical vehicle. However, the central claim of an O*(81^k) bound is not proven as written: the switch to 3-partition DP tables in Remark 24 is asserted without a definition or update rules, and the potential-function lemmas are too hand-wavy to verify the accounting. The gaps appear repairable rather than fatal, so I recommend major revision rather than rejection. I would also gently suggest that the authors verify the exact constant in Korhonen's bound, since the abstract and conclusion disagree on 1782 versus 1728."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nSome 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.\n\nWho 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.","headline":"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.","tokens_in":15432,"tokens_out":1990,"would_cite":true,"duration_ms":19077,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","68Q25","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["fixed-parameter tractability","treewidth","tree decomposition","2-approximation","linear-time algorithm","dynamic programming","potential function","graph algorithms"],"falsifier":"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.","tokens_in":14212,"feed_emoji":"🌲","tokens_out":13741,"duration_ms":101470,"temperature":0.7,"pith_summary":"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.","feed_headline":"81^k beats 1782^k for 2-approximating treewidth","feed_subtitle":"The new linear FPT algorithm cuts the exponential base from 1782 to 81 for near-optimal treewidth.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"The 2-approximation algorithm whose split-and-DP-table scheme is reorganized; the baseline whose running time is improved.","marker":"[8]"},{"why":"Provides the linear-time FPT reduction that turns a 4-approximate decomposition into an exact decision, used in Corollary 2 to remove the input-decomposition assumption.","marker":"[4]"},{"why":"Supplies the separator lemma used in Lemma 12 to prove the existence of a split when the root bag has more than $2(k+1)$ vertices.","marker":"[11]"},{"why":"Earlier linear-time 5-approximation for treewidth, representing the prior state of the art for FPT approximation with linear dependency on $n$.","marker":"[5]"}],"fun_headline_variants":["Treewidth 2-approx now 81^k: 22x faster base","Slash treewidth 2-approx base to 81^k","Treewidth: 81^k instead of 1782^k for 2-approx","2-approx treewidth in 81^k: 22x speedup"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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$.","fun_headline_variants_meta":{"raw":{"variants":["Treewidth 2-approx now 81^k: 22x faster base","Slash treewidth 2-approx base to 81^k","Treewidth: 81^k instead of 1782^k for 2-approx","2-approx treewidth in 81^k: 22x speedup"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000784,"raw_usage":{"total_tokens":3398,"prompt_tokens":817,"completion_tokens":2581,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":433,"completion_tokens_details":{"reasoning_tokens":2497}},"tokens_in":433,"tokens_out":2581,"duration_ms":16881,"temperature":1.0,"reasoning_tokens":2497,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:47:17.100061+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"A linear-time algorithm for finding tree-decompositions of small treewidth","cited_arxiv_id":null,"evidence_quote":"Provides the linear-time FPT reduction that turns a 4-approximate decomposition into an exact decision, used in Corollary 2 to remove the input-decomposition assumption."},{"cited_title":"A c^k n 5-approximation algorithm for treewidth","cited_arxiv_id":null,"evidence_quote":"Earlier linear-time 5-approximation for treewidth, representing the prior state of the art for FPT approximation with linear dependency on $n$."}],"review_version":1}