{"id":"5018c348-217d-414c-8281-f46b9e5bf394","arxiv_id":"2608.04446","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"TDPA, a treewidth dynamic program guided by heuristic 'advice' on a small modulator set, exactly completes the remaining decisions and improves MIS, MVC, and Max Cut heuristics.","lead":"Graph problems like maximum independent set are easy when the graph is tree-like, but most real graphs are not. This paper introduces a framework that lets a fast heuristic decide a few key vertices, then an exact treewidth-based dynamic program finishes the rest, improving the heuristic's solution and sometimes beating a commercial solver.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1 as printed does not implement 'conditioning on advice': unselected modulator vertices remain free in the DP, so the never-worse guarantee is unsupported by the described routine.","rationale":"The reader's conditional verdict is reasonable: the paper is ambitious and the reported trends are consistently positive. However, the strongest formal claim—TDPA yields the optimal completion conditional on the advice and hence never underperforms the base algorithm—rests entirely on Algorithm 1 and the correctness paragraph. In the pseudocode, advice is defined as a subset s⊆M, but only selected vertices are excluded from the DP's local choices (line 5), and line 7 inserts s into every bag state. Thus vertices in M\\s are not fixed to 0, and bag states can contain vertices not in the bag. The 'Correctness' discussion of boundary implications for MIS/MVC describes intended constraint propagation but does not repair these defects. Because the appendix (correctness proof, MIP formulation, full details) and the code/data are absent, a reader cannot tell whether the reported numbers come from the claimed conditional DP or from a different, less constrained routine. The proposed small exhaustive check would settle this directly. I therefore adjust the verdict from CONDITIONAL to UNVERDICTED: the central algorithmic claim is currently unverifiable, not merely missing error bars.","tokens_in":13480,"tokens_out":11629,"duration_ms":118553,"concrete_test":"Implement Algorithm 1 literally on a small graph, e.g. a 5-cycle, using the min-degree tree decomposition and M={v} for one vertex. Run MIS and MVC with advice s=∅ (meaning v is forced to 0) and compare the output to a brute-force exhaustive search over all solutions with v fixed to 0. If Algorithm 1 returns a solution that selects/includes v, or differs from the conditional optimum, then the routine is not conditioning on the full advice. Equivalently, re-derive the MVC recurrence with advice: a non-selected boundary modulator vertex must force each neighbor outside M into the cover; with s=∅, line 5 imposes no such constraint, so the recurrence will not match brute force.","verdict_should_be":"UNVERDICTED","load_bearing_attack":"The paper's strongest formal claim is that TDPA computes the optimal completion conditional on a full advice assignment over the modulator M (Section 3), and therefore never performs worse than the base algorithm. Algorithm 1 as printed does not implement this. Advice is defined as a subset s⊆M (selected vertices), but line 5 restricts only to x⊆X_t\\s; vertices in M\\s are still available to the DP, so the '0' entries of the advice are not enforced. Line 7 then adds the entire selected set s to every bag state, including vertices not in X_t, which breaks the local-state invariant required for treewidth DP. The later 'Correctness' paragraph only explains how MIS/MVC boundary implications should be propagated via ∂M; it does not repair either defect. If the implementation follows this pseudocode, TDPA is not actually conditioning on the advice: it may select vertices the advice left unselected, so the 'never worse than A' guarantee and the interpretation of Tables 1–2 as optimal completions of the advice do not follow from the described algorithm. Since the appendix (containing the correctness proof, the MIP formulation, and full details) and the code/data are unavailable, this is the central unverified step.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes TDPA, a framework that uses a treewidth modulator M to turn a heuristic algorithm A's partial decisions on M into an 'advice' string, and then runs a treewidth dynamic program that computes the optimal solution conditioned on that advice. The authors introduce a practical variant of the treewidth modulator problem, solve it with a MIP, and report experiments on Maximum Independent Set, Minimum Vertex Cover, and Max Cut, enhancing (1+1)EA, greedy heuristics, and GNN-based heuristics. The central claims are that TDPA is broadly applicable, that the enhanced version of A never performs worse than A itself, and that TDPA substantially improves solution quality, sometimes beating GUROBI. The main text defers proofs, MIP details, and further experiments to an appendix that is not present in the submitted manuscript.","tokens_in":13734,"tokens_out":8684,"duration_ms":82855,"significance":"If the formal guarantee is made correct and the missing proofs are supplied, the core idea is valuable: turning treewidth DP into a general post-processing booster rather than a standalone solver is a practically motivated and broadly applicable contribution. The paper's strength is its breadth, covering three optimization models and three very different heuristic paradigms, and its conceptual point that fixing modulator decisions can make large-treewidth instances tractable for TDP. The direct-advice version has a clean conditional-optimality property that, when correctly implemented, would justify the 'never worse' claim for that variant. However, as written, the central algorithm does not provably implement the conditioning, the formal proof is deferred, and the guarantee is overclaimed for the majority-vote and search-based variants described in Section 3.","major_comments":[{"comment":"The pseudocode does not implement advice conditioning. If the advice is a subset s⊆M of selected vertices, line 5 only restricts x to X_t\\s, so vertices in M\\s remain free to be selected by the DP; the 0-entries of the advice are not enforced. Line 7 then adds the entire set s to every bag state, including vertices that do not appear in X_t, which violates the bag-local invariant of a tree decomposition and makes the state space ill-defined. As a result, the described routine may output solutions that disagree with the advice on M\\s, and the claim in Section 1 that the TDP-enhanced version of A never performs worse than A is not supported by the algorithm as printed. The Correctness paragraph discusses boundary implications via ∂M but does not show how they are encoded in lines 5-9; a corrected pseudocode (for example, restricting each bag state to agree with a full assignment on M∩X_t) and a formal proof are needed.","section":"Section 3, Algorithm 1 (lines 5-7)"},{"comment":"The core correctness proof is missing from the manuscript. Section 3's Correctness paragraph is a sketch, and Proposition 1, Theorem 2, the MIP formulation, the min-degree heuristic, and the full proof of the advice-integrated DP are all marked (⋆) and deferred to an appendix that is not present in the submitted text. Since the 'never worse' guarantee and the interpretation of Tables 1-2 as optimal completions of the advice rest on this proof, the submission is not self-contained. The appendix must be included, or the proof must be stated in the main text, before the empirical claims can be fully evaluated.","section":"Section 3, 'Correctness' and deferred appendix"},{"comment":"The never-worse guarantee is only valid when the advice is the restriction of a single run of A; it does not automatically hold for the majority-vote advice of Algorithm 3, which may not correspond to any feasible solution of A and can be worse than the best individual run. Moreover, Section 4 does not state whether Table 2 reports WTA or Maj results, so the reader cannot tell which variant produced the reported improvements. The same caveat applies to the (1+1)EA subroutine, where the final advice is found by search rather than taken directly from the baseline's output. The paper should explicitly restrict the formal guarantee to the direct-advice setting and report the voting rule used in each experiment.","section":"Section 3, 'ϵ-greedy with Voting Subroutine' and Section 4"},{"comment":"The headline claim that TDP-enhanced greedy heuristics 'clearly outperform' GUROBI is not supported by the reported statistics. Table 2 gives only aggregate averages over 100 instances; no standard deviations, per-instance wins, or significance tests are provided, and the differences are in some cases a few tenths of a percent (e.g., MIS on ER: -0.20% vs 0.00% for GUROBI-600s). The comparison is also asymmetric in time, which is a strength, but the negative gaps should be accompanied by confidence intervals or paired differences. Please report the full distribution or the number of instances where TDPA is better, equal, and worse.","section":"Section 4, Table 2"}],"minor_comments":[{"comment":"The sentence 'To demonstrate the general applicability of our proposed framework. We experimented...' is a sentence fragment; it should be joined with the following clause.","section":"Abstract"},{"comment":"The definition of TM-stability uses Lp and Lc before defining them: the text says 'defined at checkpoint t as |Lp∩Lc|/|M|, where Lt is the predicted label set onM.' This should say L_t and clarify the relationship between Lp, Lc, and L_t.","section":"Section 4, GNN paragraph"},{"comment":"The tables C and D are not initialized or described; the merge and upload formulas in lines 8-9 are not self-contained and should reference the standard TDP definitions or specify the domains of C and D.","section":"Algorithm 1"},{"comment":"For MVC, the implication 'excluding v∈∂M forces all neighbors v∈N(v) to be included' should specify that this applies to neighbors outside M as well, and the analogous implications for MIS should be stated for all neighbors, not only those in the current bag.","section":"Section 3, Correctness paragraph"},{"comment":"No code or data availability statement is provided; given the empirical nature of the paper and the many deferred implementation details, including a public repository or an appendix with the exact MIP formulation and solver settings would improve reproducibility.","section":"General"},{"comment":"The paper switches between describing advice as a subset s⊆M and as a bitvector x∈{0,1}^|M|; the conversion between these two representations should be stated explicitly to avoid ambiguity.","section":"Notation, Section 3"}],"recommendation":"major_revision","confidential_remarks":"The core idea is appealing and the empirical direction is promising, but the current version is not self-contained: the correctness proof is deferred, the main algorithm's pseudocode appears inconsistent with the claimed conditioning, and the 'never worse' guarantee is stated more broadly than the described variants justify. These are fixable within the manuscript's scope, so I recommend major revision rather than rejection. The authors should also be asked to state which voting rule was used in the experiments and to provide per-instance statistics for the GUROBI comparisons."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Good idea hiding behind a sloppy formal writeup. The proposal is to take a heuristic's decisions on a small modulator (backdoor) and let treewidth DP optimize the rest exactly. If that works, it's a genuinely general plug-in booster, and the paper tests it on three problems and three heuristic families, which is more than most such papers bother with. The empirical gains look consistent, and the authors deserve credit for the large experimental effort and for not hiding the modulator optimality gap.\n\nNow the soft spots, and one is serious. Algorithm 1 as printed does not implement conditioning on the advice. Line 5 builds states x ⊆ X_t \\ s, which actually forbids selecting the advice's chosen vertices, and line 7 then sticks the entire set s into every bag state, including vertices outside the bag, which breaks the invariant of treewidth DP. The correctness paragraph in Section 3 talks about boundary propagation via ∂M, but it doesn't repair either defect. So the 'never worse than A' guarantee is not supported by the described routine. That's the load-bearing step, and the proof is in the missing appendix. The guarantee is also overclaimed for the majority-vote and EA-search variants: it holds for the direct pipeline where you take A's output as advice and complete optimally, not for a vote that might create an advice string no single run produced. The broader 'for any existing algorithm A' phrasing needs qualification.\n\nOther issues are more standard: no code, no data, no error bars or significance tests, MIP formulation deferred. The '1 second on average' claim needs detail.\n\nNone of this kills the idea. The practical setup—compute a small modulator via MIP on a fixed tree decomposition, then run TDP on the remainder—is plausible, and the GNN early-stopping observation (TM-stability) is a nice extra. But as submitted, the paper cannot be checked: the central pseudocode mismatches the claim, and the appendix/code are absent. I'd send it to review with a strong request to fix Algorithm 1, provide the missing material, and qualify the guarantee to what actually holds. The right audience is people doing practical parameterized algorithms or heuristic-boosting; they'd get real value if the details are tightened.","headline":"A useful booster idea with broad experiments, but the printed Algorithm 1 doesn't do what the main guarantee claims; fix the pseudocode and ship the appendix/code before trusting the results.","tokens_in":14250,"tokens_out":3816,"would_cite":true,"duration_ms":36367,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Treewidth dynamic programming can serve as a general performance booster for graph optimization heuristics.","keywords":["treewidth","treewidth modulator","treewidth dynamic programming","advice string","maximum independent set","minimum vertex cover","max cut","graph neural networks"],"falsifier":"Run TDPA on a family of graphs whose true minimum treewidth modulator is provably large, for example expanders with treewidth linear in $n$, and compare against the base heuristic; if solution quality does not improve in that regime, the booster's usefulness is limited to graphs that already admit small modulators.","tokens_in":13293,"feed_emoji":"🧩","tokens_out":16065,"duration_ms":122971,"temperature":0.7,"pith_summary":"This paper argues that treewidth dynamic programming (TDP), normally impractical once treewidth grows beyond a small constant, can be repurposed as a general booster for existing graph optimization heuristics. The recipe is to find a small vertex set called a treewidth modulator whose deletion leaves the graph with small treewidth, let the base heuristic fix the decisions on those vertices, and let TDP solve everything else exactly. Because TDP completes any advice optimally, the enhanced algorithm is guaranteed never to produce a worse solution than the base algorithm. On Maximum Independent Set, Minimum Vertex Cover, and Max Cut, the paper reports that evolutionary, greedy, and graph-neural-network heuristics all improve, and that enhanced greedy sometimes matches or beats a commercial solver.","feed_headline":"Treewidth DP boosts the heuristics it is paired with","feed_subtitle":"Advice on a small vertex set lets treewidth DP finish the job, improving every tested baseline.","key_machinery":"The load-bearing object is an $\\eta$-treewidth modulator: a vertex set $M_\\eta$ whose removal leaves a graph of treewidth at most $\\eta$. The framework takes a tree decomposition, finds a small modulator by solving a mixed-integer program over the existing bags, uses the base algorithm's output on $M_\\eta$ as the advice, and then runs treewidth dynamic programming over the low-treewidth remainder, enforcing boundary consistency on the modulator boundary. The paper proves that the modulator-finding variant on a given tree decomposition is NP-complete, yet reports that it solves in about one second on average in the experiments, and that the advice-conditioned DP is correct.","core_discovery":"The central claim is that TDP with advice (TDPA) turns treewidth dynamic programming from a standalone solver for tiny-treewidth graphs into a general enhancer: for any existing algorithm $A$, run $A$ on a treewidth modulator, treat its output on those vertices as an advice string, and run a modified TDP that is optimal conditional on that string. The resulting solution is never worse than $A$'s, because any completion $A$ could reach is also available to the DP, and in practice it is frequently much better. Empirically the paper finds that TDPA improves (1+1)EA, epsilon-greedy heuristics, and GNN-based solvers across three NP-hard optimization problems, and that TDP-enhanced greedy is competitive with, and sometimes better than, the commercial solver used as reference.","pith_inferences":["A consequence the paper leaves implicit is that a heuristic's practical value might be assessed by the quality of its decisions on the modulator alone, since TDP repairs the rest optimally.","The same advice-conditioning pattern should transfer to other width parameters such as pathwidth or branchwidth, and to constraint-satisfaction settings where a small backdoor set exists.","The TM-stability plateau suggests a direct training intervention: once stability is detected, bias GNN gradient updates toward the modulator vertices instead of continuing to train on vertices that TDP can fix exactly.","The majority-vote version of the greedy advice can be viewed as a small ensemble over repeated runs, leaving open how much of the reported benefit comes from voting rather than from the single best run."],"forward_implications":["Any existing heuristic $A$ can be wrapped so that the result is never worse in solution quality than $A$, at the price of building a tree decomposition and modulator once.","TDP ceases to be limited to graphs of tiny treewidth: the relevant quantities become the modulator size and the remaining treewidth, not the original treewidth.","Heuristic tuning becomes less brittle; exploration rates that hurt standalone greedy no longer degrade quality much once TDP completes the advice.","For GNN-based solvers, the modulator-stability signal gives an early-stopping rule: once labels on the modulator freeze, further training mostly reshuffles decisions that TDP can already optimize exactly.","On several harder instances, TDP-enhanced greedy matches or exceeds the commercial solver reference, sometimes in less wall-clock time, despite a pure-Python implementation."],"supporting_citations":[{"why":"Gives the MSO theorem that makes hard graph problems linear-time solvable on bounded-treewidth graphs, the theoretical foundation of TDP.","marker":"[Courcelle, 1990]"},{"why":"Introduces the treewidth-modulator notion and its parameterized hardness, grounding the paper's use of modulators.","marker":"[Cygan et al., 2011]"},{"why":"Shows vertex deletion for hereditary properties is NP-complete, justifying the practical heuristic modulator search.","marker":"[Lewis and Yannakakis, 1980]"},{"why":"Supplies the min-degree tree-decomposition heuristic the paper uses to build initial decompositions.","marker":"[Bannach et al., 2017]"},{"why":"Reports near-optimal practical treewidth on real-world graphs, supporting both the decomposition heuristic and the EASY dataset.","marker":"[Maniu et al., 2019]"},{"why":"Supplies the backdoor concept from SAT on which the advice-string idea is built.","marker":"[Williams et al., 2003]"},{"why":"Provides the standard treewidth dynamic-programming exposition that Algorithm 1 modifies to accept advice.","marker":"[Cygan et al., 2020]"},{"why":"Is the commercial solver used as the reference baseline for solution quality and runtime comparisons.","marker":"[Gurobi Optimization, LLC, 2024]"},{"why":"Supplies a maximum-independent-set GNN baseline that TDPA enhances and diagnoses.","marker":"[Ahn et al., 2020]"},{"why":"Supplies a diffusion-style GNN baseline and the hard-instance generation model used in the experiments.","marker":"[Sun and Yang, 2023]"}],"fun_headline_variants":["Treewidth DP with advice boosts any graph heuristic","Modulator advice turns treewidth DP into a universal booster","Boosting any graph heuristic with treewidth modulators","Treewidth DP enhances any algorithm via modulator advice"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The framework works if the target graphs admit a small treewidth modulator that the MIP heuristic can find quickly, if the remaining treewidth stays small enough for TDP to be fast, and if the base algorithm's advice on the modulator is informative; the paper itself notes its modulator can be far from the optimal one.","fun_headline_variants_meta":{"raw":{"variants":["Treewidth DP with advice boosts any graph heuristic","Modulator advice turns treewidth DP into a universal booster","Boosting any graph heuristic with treewidth modulators","Treewidth DP enhances any algorithm via modulator advice"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000493,"raw_usage":{"total_tokens":2440,"prompt_tokens":982,"completion_tokens":1458,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":598,"completion_tokens_details":{"reasoning_tokens":1396}},"tokens_in":598,"tokens_out":1458,"duration_ms":9446,"temperature":1.0,"reasoning_tokens":1396,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:40:16.458056+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run TDPA on a family of graphs whose true minimum treewidth modulator is provably large, for example expanders with treewidth linear in $n$, and compare against the base heuristic; if solution quality does not improve in that regime, the booster's usefulness is limited to graphs that already admit small modulators.","supporting_citations":[{"cited_title":"The monadic second- order logic of graphs","cited_arxiv_id":null,"evidence_quote":"Gives the MSO theorem that makes hard graph problems linear-time solvable on bounded-treewidth graphs, the theoretical foundation of TDP."},{"cited_title":"On the hardness of losing width.Theory of Computing Systems, 54:73–82,","cited_arxiv_id":null,"evidence_quote":"Introduces the treewidth-modulator notion and its parameterized hardness, grounding the paper's use of modulators."},{"cited_title":"Lewis and Mihalis Yannakakis","cited_arxiv_id":null,"evidence_quote":"Shows vertex deletion for hereditary properties is NP-complete, justifying the practical heuristic modulator search."},{"cited_title":"Jdrasil: A modular library for computing tree decompositions","cited_arxiv_id":null,"evidence_quote":"Supplies the min-degree tree-decomposition heuristic the paper uses to build initial decompositions."},{"cited_title":"An experimental study of the treewidth of real-world graph data (extended version)","cited_arxiv_id":null,"evidence_quote":"Reports near-optimal practical treewidth on real-world graphs, supporting both the decomposition heuristic and the EASY dataset."},{"cited_title":"Backdoors to typical case complexity","cited_arxiv_id":null,"evidence_quote":"Supplies the backdoor concept from SAT on which the advice-string idea is built."},{"cited_title":"Fomin, Lukasz Kowa- lik, Daniel Lokshtanov, D ´aniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh","cited_arxiv_id":null,"evidence_quote":"Provides the standard treewidth dynamic-programming exposition that Algorithm 1 modifies to accept advice."},{"cited_title":"Gurobi Optimizer Reference Manual,","cited_arxiv_id":null,"evidence_quote":"Is the commercial solver used as the reference baseline for solution quality and runtime comparisons."},{"cited_title":"Learning what to defer for maximum independent sets","cited_arxiv_id":null,"evidence_quote":"Supplies a maximum-independent-set GNN baseline that TDPA enhances and diagnoses."}],"review_version":2}