{"id":"a2d9882f-f2cb-4efe-b6ca-0ec3fafe5fd4","arxiv_id":"2607.07595","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Bounded induced-H-packing treewidth, a new decomposition parameter generalizing tree-independence number, yields quasipolynomial-time algorithms for MWIS, list 3-coloring, and odd cycle transversal for several choices of H.","lead":"The paper introduces induced-H-packing treewidth, a measure of how many disjoint induced copies of a graph family H can touch any bag of a tree decomposition. It then proves quasipolynomial-time algorithms for MWIS, list 3-coloring, and odd cycle transversal on graphs where this measure is bounded, and small dominated separators when H contains a path or all cycles.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The all-cycles separator theorem rests entirely on an unproved external result (Theorem 8.2) cited only as a YouTube video; if that theorem is false or weaker than stated, the cycle case of the main claim collapses.","rationale":"I read the paper in good faith and checked the main proof threads. The container lemma for MWIS (Lemma 4.1) is detailed and appears sound. The modular-decomposition argument for P4, the P5 list-coloring argument (modulo a briefly sketched but plausible container lemma for list 3-coloring), the OCT reduction via layer-connected components, and the blob-graph applications are internally coherent. The path case of the dominated-separator theorem is self-contained and correct. The cycle case, however, leans on Theorem 8.2, which is cited only as a YouTube video. That theorem is exactly the step that converts the absence of a large induced B-cycle packing into a bounded set of neighborhoods hitting all B-cycles; without it, the induction in Lemma 8.3 cannot start. This matches the reader's weakest_assumption. I also noted minor presentation issues—Lemma 4.2 is only sketched, and the subdivided-claw hardness proof in §10.1 has an off-by-one/definitional ambiguity in the construction of S(v)—but these are peripheral or readily fixable and do not change the primary concern. The appropriate verdict remains CONDITIONAL: the central framework is promising and most proofs are solid, but the all-cycles results need a citable written proof of Theorem 8.2 before the claims can be accepted unconditionally.","tokens_in":41143,"tokens_out":27435,"duration_ms":284001,"concrete_test":"Obtain the full proof behind the Ahn–Kwon video [3] and check whether it establishes exactly Theorem 8.2: for every graph G, every set B, and every k, if there are no k+1 pairwise anticomplete induced B-cycles then there is a set Y of size O(k^3) such that G−N[Y] has no B-rooted cycle. In particular, trace the k=2 case through the proof and verify the constant; also verify the footnote's claim that every non-induced (3,B)-cycle contains an induced B-cycle on a subset of its vertices. If the theorem cannot be reproduced from the cited source, Lemma 8.3 and the all-cycles algorithmic consequences are unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1.6(2) and Corollary 1.7 for families H containing all cycles depend on Lemma 8.3, whose proof invokes Theorem 8.2 as its only source for an O(k^3)-vertex set Y with G−N[Y] B-cycle-free. Theorem 8.2 is an induced Erdős–Pósa property for B-rooted cycles: from the absence of k+1 pairwise anticomplete induced cycles intersecting B, it gives a bounded hitting set Y with |Y|=O(k^3) whose closed neighborhood intersects every B-rooted cycle. This is not a minor black-box application; it is the engine of the whole cycle case. Without it, Lemma 8.3 has no way to eliminate all B-cycles before descending into the heavy component, so the O(k^3 log n) dominated separator, the QPTAS for MWIS, and the subexponential algorithms for the all-cycles case do not follow. The paper cites only an online video [3] rather than a written proof or published article, and the footnote's claimed equivalence between non-induced (3,B)-cycles and induced B-cycles is asserted without proof. This is an external verifiability gap, not an identified internal contradiction, but it is the weakest point in the central argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces induced-\\mathcal{H}-packing treewidth, a tree-decomposition parameter measuring, for each bag, the maximum size of a family of pairwise anticomplete induced copies of graphs from a fixed family \\mathcal{H} that all meet the bag. It observes that this parameter generalizes tree-independence number and induced matching treewidth, and it claims a broad algorithmic program: quasipolynomial-time MWIS when \\mathcal{H} contains P_4, quasipolynomial-time List 3-Coloring when \\mathcal{H} contains P_5, quasipolynomial-time Odd Cycle Transversal and a QPTAS for hereditary bounded-treewidth CMSO_2 problems when \\mathcal{H} contains P_3, and dominated balanced separators (with resulting QPTAS and subexponential algorithms) when \\mathcal{H} contains a fixed path or all cycles. The paper also gives an XP approximation algorithm for computing the new parameter and NP-hardness/inapproximability lower bounds. The P_3, P_4, and P_5 algorithm sections and the path-separator lemma are supported by detailed proofs; the all-cycles separator theorem rests on an external result cited only as a video.","tokens_in":41388,"tokens_out":17621,"duration_ms":171686,"significance":"If the main claims hold, this is a valuable unifying framework. The parameter definition is clean and non-circular: it generalizes known parameters, reduces to them in special cases, and connects a broad family of algorithmic results to a single container-plus-recursion template. The paper contains several genuinely useful technical contributions: the MWIS container lemma with a clear branching potential, the modular-decomposition handling of (B,P_4)-clean graphs, the (B,P_5)-clean decomposition for List 3-Coloring, the two-layer reduction for OCT, and the blob-graph stability result. The decomposition approximation and hardness results are also well organized. However, two load-bearing points are not in final verifiable form: the all-cycles separator theorems depend on a theorem cited only as a YouTube video, and the List 3-Coloring container lemma is only sketched. These must be remedied before the central claims can be considered established.","major_comments":[{"comment":"The all-cycles case of Theorem 1.6 and Corollary 1.7 rests entirely on the induced Erdős–Pósa theorem for B-rooted cycles, stated as Theorem 8.2 and cited only as an online video [3]. This is not a peripheral black box: Lemma 8.3 uses it to produce the O(k^3) set Y, and without that set the weighted-separator induction and the O(k^3 log n) bound do not go through. A published theorem cannot rest on a video citation. Please supply a complete proof of Theorem 8.2, or replace [3] by a written peer-reviewed source, or restrict the claims that depend on it. The footnote asserting equivalence between non-induced (3,B)-cycles and induced B-cycles is also asserted without proof; if the external theorem is used in that translated form, the translation needs a proof.","section":"§8.2, Theorem 8.2, Lemma 8.3"},{"comment":"Lemma 4.2 is the container lemma for List 3-Coloring and is load-bearing for Theorem 1.3 and hence for the abstract's P_5 claim. However, the proof is explicitly only a sketch. The key branching measure U^* requires a precise invariant after exhaustive application of the reduction rules: one needs a formal argument that at every processed node all lists have size at least 2, that the chosen color i lies in A ∩ L'(x), and that the size of U^* decreases by a constant fraction in both branches even after the reduction rules are re-applied. The sketch asserts these facts but does not prove them. Please provide a full proof or a detailed formal treatment in the paper or an appendix.","section":"§4, Lemma 4.2"},{"comment":"The construction in the proof of Theorem 10.1 appears incorrect. After subdividing every edge of a cubic graph 2t times, the set S(v) of vertices at distance t from a core vertex v is an independent set of three vertices: the three chosen vertices are pairwise at distance 2t via v and hence are pairwise non-adjacent. Such a set is not isomorphic to a subdivided claw unless the subdivided claw is a single vertex. Consequently the claimed decomposition with tree-π_H(G')=1 is not justified, and the hardness conclusion over graphs of tree-π_H=1 does not follow. Either replace S(v) by the ball of radius t around v and rework the packing-number verification, or delete/qualify this negative result.","section":"§10.1, Theorem 10.1"}],"minor_comments":[{"comment":"The text first sets F(n)=2^{O(log^3 n)} and then concludes F(n)=n^{O(log^2 n)}. This is correct only because 2^{O(log^3 n)}=n^{O(log^2 n)}; the equality should be stated explicitly to avoid the appearance of a mismatch with the theorem statement.","section":"§6.4, proof of Theorem 6.4"},{"comment":"The proof of the monotonicity tree-π_{P_{t+1}} ≤ tree-π_{P_t} chooses a t-vertex subpath of each path; it should state explicitly that the chosen subpaths remain pairwise anticomplete, since they are subgraphs of pairwise anticomplete paths. The argument is clear but a one-line justification would help.","section":"§3, Lemma 3.2(3)"},{"comment":"Reference [3] is a YouTube video. Independent of the major issue, the paper should give a publication venue or arXiv identifier if one becomes available, and should distinguish the video's content from the theorem statement used here.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The path-case algorithms and the parameter framework are promising and the MWIS container proof is detailed. The main obstacle is external verification: the all-cycles separator theorem sits on an unpublished video citation, the List 3-Coloring container lemma is only sketched, and Section 10.1 contains a concrete-looking construction error. These are fixable within the manuscript's scope, so I do not recommend reject, but they must be resolved before the cycle-case claims can be relied on."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. First, the induced-H-packing treewidth parameter is a good idea and it does real work: it subsumes tree-independence number and induced matching treewidth, and the paper gets new quasipolynomial algorithms for MWIS, List 3-Coloring, OCT, and a QPTAS for hereditary (tw≤r, ψ)-MWIS across a range of H. That is a genuine contribution, not just a repackaging. Second, the paper has two soft spots that are specific and addressable: the container lemma for List 3-Coloring (Lemma 4.2) is only sketched, and the entire all-cycles separator theorem depends on an external result (Theorem 8.2) cited to an online video rather than a written proof. If that external theorem is false or weaker than stated, the cycle case of Theorem 1.6 collapses.\n\nWhat is actually new: the parameter itself, the equivalences for P1 and P2 are observations but the P3/P4/P5 results are new, and the dominated-balanced-separator theorems for paths and cycles are new structural results. The path case (Lemma 8.1) is self-contained and elegant: Gyárfás path argument plus a bounded packing around the central bag gives a constant-size dominated separator. The P4 MWIS section has a nice interaction between modular decomposition and (B, P4)-clean graphs. The P5 List 3-Coloring section is intricate but appears to be detailed and sound. The hardness reductions for computing the parameter are clean.\n\nThe soft spots, in proportion: Lemma 4.2 is load-bearing for Theorem 1.3 but the proof is a sketch that says \"essentially the same as Theorem 4.1\" with a few paragraphs. This is probably fixable, but it is the kind of thing referees will want to see fully. More seriously, Lemma 8.3 uses Theorem 8.2 as its only engine for the cycle case. That theorem is an induced Erdős–Pósa property for B-rooted cycles with O(k^3) hitting set, and the citation is a YouTube video from 2026. The footnote trying to equate the non-induced (3,B)-cycles in the video with induced B-cycles is asserted without proof, and the equivalence is not obvious. If this external theorem is missing hypotheses or has a different constant, then the cycle separator, the QPTAS for MWIS in that case, and part of the answer to Bodlaender–Fomin–Korhonen do not follow.\n\nThe paper deserves a serious referee. It is not desk-reject material; it is a substantial theory paper with mostly careful proofs. But I would send it back with the requirement that the authors provide a full proof of Lemma 4.2 and a citable written source (or a complete proof in the appendix) for Theorem 8.2. The central argument is sound where I checked it; these are verifiability gaps, not internal contradictions.","headline":"A serious unifying framework for structured tree decompositions with real quasipolynomial algorithms, but the all-cycles separator rests on an unverified external theorem cited only as a YouTube video.","tokens_in":41933,"tokens_out":1043,"would_cite":true,"duration_ms":13610,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","05C69","05C38"],"pacs":[],"model":"deepseek-v4-flash","headline":"Bounded induced-H-packing treewidth—a tree-decomposition parameter measuring how many anticomplete induced copies of H can meet a bag—yields quasipolynomial-time algorithms for maximum-weight independent set, list 3-coloring, and odd cycle","keywords":["induced packing treewidth","tree decomposition","maximum weight independent set","list 3-coloring","odd cycle transversal","Erdős–Pósa property","quasipolynomial time","blob graphs"],"falsifier":"A counterexample to that Erdős–Pósa claim: construct a graph G and set B with no two anticomplete induced B-cycles, yet every set of fewer than c k^3 vertices fails to hit all B-cycles in the sense that G−N[Y] still contains a B-rooted cycle; if such graphs exist for unbounded k, the O(k^3 log n) separator bound would fail.","tokens_in":40989,"feed_emoji":"","tokens_out":5008,"duration_ms":47634,"temperature":0.7,"pith_summary":"This paper introduces induced-H-packing treewidth, a parameter that assigns to each graph the minimum, over all tree decompositions, of the maximum number of pairwise anticomplete induced copies of graphs from H that intersect a single bag. It generalizes two known parameters: tree-independence number (when H={P1}) and induced matching treewidth (when H={P2}). The authors show that boundedness of this parameter yields quasipolynomial-time algorithms for Maximum-Weight Independent Set when H contains P4, List 3-Coloring when H contains P5, and Odd Cycle Transversal when H contains P3; they also obtain a QPTAS for finding large induced subgraphs of bounded treewidth satisfying a hereditary formula when P3 is present, and a QPTAS for MWIS when H contains all cycles or any path. These results partially answer a recently posed open question about P3- and cycle-packing tree decompositions.","feed_headline":"Quasipolynomial algorithms from bounded induced-packing treewidth","feed_subtitle":"New parameter unifies forbidding induced subgraphs with structured bags, answering open questions on P3- and cycle-packings.","key_machinery":"The central object is the parameter induced-H-packing treewidth, denoted tree-π_H(G): the minimum, over all tree decompositions of G, of the maximum number of pairwise anticomplete induced copies of graphs from H that intersect a common bag. Two workhorses carry the argument: (1) container lemmas that, for a bag B with bounded packing number, enumerate a quasipolynomial-size family of (B,H)-clean induced subgraphs that preserve the existence (or optimal weight) of independent sets or list 3-colorings, and (2) the blob graph G∘, whose vertices are connected vertex sets of G, which maps induced packings to independent sets and preserves bounded tree-π_{P3}. The cycle case also relies on an ind","core_discovery":"The central claim is that many classes defined by forbidden induced subgraphs or induced minors can be captured by a single structural parameter: induced-H-packing treewidth. For a fixed family H, the parameter is computed by taking a tree decomposition and, for each bag, counting the largest number of pairwise anticomplete induced copies of graphs from H that all intersect that bag; the width is the minimum of this count over all decompositions. The paper proves that when this parameter is bounded by a constant, a range of problems become tractable in quasipolynomial time: MWIS for H containing P4, List 3-Coloring for H containing P5, Odd Cycle Transversal for H containing P3, and QPTASes f","pith_inferences":["The framework likely extends to subdivided claws: the paper conjectures that bounded induced-subdiv(K_{1,3})-packing treewidth makes MWIS tractable, leaving a concrete open direction.","If the cited induced Erdős–Pósa property for B-rooted cycles holds with polynomial bounds as stated, the separator results transfer directly to any family containing all cycles; a written proof would solidify this dependence.","The container-lemma recursion may be tightenable to polynomial time for specific H, which would answer a natural open question about when quasipolynomial can be improved.","The parameter offers a new bridge toward the broader conjectures on induced-minor-free classes, suggesting that separator-and-container techniques could be exported beyond the linear-forest case."],"forward_implications":["Maximum-Weight Independent Set and List 3-Coloring become quasipolynomial-time solvable in graphs of bounded induced-H-packing treewidth when H contains P4 or P5, respectively.","Odd Cycle Transversal and (tw≤r,ψ)-MWIS admit quasipolynomial-time approximation schemes when H contains P3.","Every graph of bounded tree-π_H admits a balanced separator dominated by O(kt) vertices if H contains a t-vertex path, and by O(k^3 log n) vertices if H contains all cycles.","A tree decomposition of induced-H-packing number at most 8k can be computed in time 2^{O(k^2)} n^{O(k)} when it exists, and the parameter is NP-hard to compute exactly.","These results partially resolve the previously open question on P3- and cycle-packing treewidth tractability."],"fun_headline_variants":["Induced-packing treewidth unifies forbidden subgraphs and decompositions","Bounded induced-packing treewidth yields quasipolynomial algorithms","Quasipolynomial time from induced-packing treewidth","Tree parameter answers P3 and cycle open questions","Induced-packing treewidth: unifying forbidden patterns and bags"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The cycle part of the dominated-separator theorem rests on an induced Erdős–Pósa property for B-rooted cycles—the claim that the absence of k+1 pairwise anticomplete such cycles forces a hitting set of O(k^3) vertices—which is cited only as an online video rather than a written proof.","fun_headline_variants_meta":{"raw":{"variants":["Induced-packing treewidth unifies forbidden subgraphs and decompositions","Bounded induced-packing treewidth yields quasipolynomial algorithms","Quasipolynomial time from induced-packing treewidth","Tree parameter answers P3 and cycle open questions","Induced-packing treewidth: unifying forbidden patterns and bags"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000511,"raw_usage":{"total_tokens":2344,"prompt_tokens":788,"completion_tokens":1556,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":532,"completion_tokens_details":{"reasoning_tokens":1470}},"tokens_in":532,"tokens_out":1556,"duration_ms":12521,"temperature":1.0,"reasoning_tokens":1470,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T01:57:15.243175+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A counterexample to that Erdős–Pósa claim: construct a graph G and set B with no two anticomplete induced B-cycles, yet every set of fewer than c k^3 vertices fails to hit all B-cycles in the sense that G−N[Y] still contains a B-rooted cycle; if such graphs exist for unbounded k, the O(k^3 log n) separator bound would fail.","supporting_citations":[],"review_version":4}