{"id":"4b6546e5-0af7-4ae5-a7ab-4235c7773027","arxiv_id":"2608.09800","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Pathwidth-eta Deletion admits a uniform polynomial kernel of size O(|M|^3) when a vertex cover M is given, unlike Treewidth-eta Deletion.","lead":"The paper proves that Pathwidth-eta Deletion, a graph cleanup problem where you delete at most k vertices to make the remaining graph have low pathwidth, can be compressed into small equivalent instances with bounds that do not depend on eta in the exponent. It shows pathwidth behaves like treedepth rather than treewidth, which changes expectations for this family of parameterized problems.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"For β=0, Definition 5.12 sets B2=0, so B#marked=0; Algorithm 3 calls Lemma 5.11 with c=0 although c≥2 is required, making ReduceModulatorDegree undefined for the dist-to-pathwidth-1 case advertised in Corollary 1.4(2).","rationale":"The paper's technical machinery—the component-reduction rule, the virtual-clique/polishing-set framework, the caterpillar rules, and the protrusion-size reduction—is detailed and, as far as I checked, internally consistent. I did not find a fatal flaw in the main arguments for β≥1. I also do not regard Theorem 3.15 as the main soft spot: given Bulian–Dawar's decision oracle for constant elimination distance, the standard recursion over a guessed root and the connected components after deleting it does produce a nice elimination tree of depth at most β, so the reader's weakest-assumption concern is addressable. The concrete gap I found is the β=0 boundary case in the degree-reduction constants. Since Main Theorem 1 claims all β≥0 and Corollary 1.4(2) relies on the β=0 case, the proof needs a small but explicit fix before the stated results are fully established. This is not a rejection-level issue, but it does justify a conditional acceptance: the authors should patch the β=0 constants or add a separate argument for dist-Gpw≤1.","tokens_in":63423,"tokens_out":40097,"duration_ms":364501,"concrete_test":"Run the reduction on a β=0 instance: let G−M be a single path (or caterpillar) with pathwidth 1, and let M contain one vertex m adjacent to a vertex of C. Compute B#marked from Definition 5.12; it is 0. Check whether Lemma 5.11 can be applied with c=0 in Lemma 5.16/Algorithm 3, Line 16. It cannot, since the lemma requires c≥2 and a depth-0 elimination forest (a single leaf) has no children from which to choose B1 unmarked children. Then re-run the algorithm with the proposed patch, e.g., B2 := max(1,2βB1), and verify that ReduceDegreeTree is no longer entered for β=0 and that all subsequent size bounds still hold.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Definition 5.12 defines B2 = 2β·B1. For β=0, B2=0 and therefore B#marked = f5.11(B2,1) = (β+1)·(B2)^(β+1) = 0. Lemma 5.11 is stated only for integers c≥2, and its proof needs c≥2 to bound the number of parents of a large set. In Lemma 5.16, Algorithm 3's Line 16 is justified by applying Lemma 5.11 with c = B#marked; for β=0 this is an invalid invocation. This is not a harmless degenerate case: β=0 is exactly G^0_{pw≤η}, the pathwidth-1 distance case used by Corollary 1.4(2). Worse, in Algorithm 2 the branch condition is 'm has more than BF(|NG(C)|) F-neighbors', and BF(x) = (β+1)·B3(x) = 0 when β=0. Hence whenever a modulator vertex has any neighbor in a pathwidth-1 component, the algorithm enters the broken ReduceDegreeTree branch instead of reaching the caterpillar-reduction branch. The gap is patchable—for example by setting B2 := max(1,2βB1) or by handling β=0 separately before the degree-reduction step—but as written the proof of Main Theorem 1 for β=0 is incomplete.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Pathwidth-η Deletion parameterized by the size of a modulator M such that G−M has pathwidth at most η and elimination distance at most β to pathwidth-1 graphs. The main result (Main Theorem 1) is a kernel on g(η,β)·|M|^60 vertices with the exponent independent of η and β, and the kernel outputs a minor of the input graph. As corollaries, the paper obtains uniform polynomial kernels for parameterization by vertex cover number (Corollary 1.5), by distance to pathwidth-1 graphs, by distance to treedepth η+1, and others. The paper also derives bounds on the size of minor-minimal obstructions to k-apices of pathwidth-η graphs, contrasting with a new lower-bound construction for treewidth (Theorem 1.9). The proof is built from a reduction rule for the number of connected components (Theorem 2.1), a degree-reduction rule for modulator vertices using elimination forests (Lemma 2.4), a caterpillar reduction rule (Lemma 2.5), and a protrusion-reduction step (Section 6).","tokens_in":63714,"tokens_out":14841,"duration_ms":116345,"significance":"If the proof is correct, this is a substantial contribution: it provides the first uniform polynomial kernel for Pathwidth-η Deletion under several structural parameterizations, resolving the question in the affirmative for these parameterizations and showing a rare algorithmic divergence between pathwidth and treewidth. The paper is technically detailed, states exact functions and bounds for each reduction rule, and the kernel outputs a minor of the input graph, which yields elegant obstruction-size consequences. However, as discussed in the major comments, the proof currently has a load-bearing gap for the case β=0, which is precisely the parameterization advertised in Corollary 1.4(2). The gap appears repairable by adjusting the constants in Definition 5.12, but the current manuscript does not prove Main Theorem 1 for all stated values of β.","major_comments":[{"comment":"The proof of Main Theorem 1 is incomplete for β=0, which is included in the theorem statement and is exactly the case used by Corollary 1.4(2) (Pathwidth-η Deletion/dist-G_{pw≤1}). In Definition 5.12, B2 is defined as 2β·B1, so for β=0 we have B2=0 and consequently B#marked=f5.11(B2,1)=0. Lemma 5.16 then justifies Line 16 of Algorithm 3 by applying Lemma 5.11 with c=B#marked=0, but Lemma 5.11 is stated only for integers c≥2 and its proof divides by c. Furthermore, in the soundness proof of Algorithm 3, Claim 5.20 requires the inequality B2≥f4.3(B0+β)+B0+1, which is false for β=0 because the right-hand side is positive while B2=0. At the level of Algorithm 2, the branch condition in Line 12 tests whether m has more than BF(|NG(C)|) F-neighbors; since BF(x)=(β+1)·B3(x)=0 for β=0, any modulator vertex with at least one neighbor in C enters the invalid ReduceDegreeTree branch, making the caterpillar-reduction branch (Lines 15–17) unreachable even though for β=0 the elimination tree F consists of a single leaf and the intended reduction would be the caterpillar rule. This gap is load-bearing and should be repaired, for instance by redefining B2 to be at least max(2, 2βB1, f4.3(B0+β)+B0+1) and rechecking the downstream inequalities, or by handling β=0 as a separate case.","section":"Definition 5.12, Lemma 5.16, Algorithm 3, Claim 5.20, Algorithm 2, Corollary 1.4(2)"}],"minor_comments":[{"comment":"The statement that a nice G_{pw≤1}-elimination tree of depth at most β can be computed in polynomial time is justified only by a brief reference to [14, Corollary 1] and a short guessing argument; since all depth-sensitive bounds in Sections 5.3 and 6.2 depend on the depth bound and niceness, please expand this into a self-contained proof or a precise extraction from the cited work.","section":"Section 3.5, Theorem 3.15"},{"comment":"Many mathematical expressions have lost their superscripts in typesetting, e.g., f5.11(c,x)=(β+1)c^{β+1}x and the definitions of B#marked and B3 in Definition 5.12 appear without the exponent on B2; please ensure the camera-ready version uses correct math typesetting.","section":"Throughout (e.g., Definition 5.12)"},{"comment":"The sentence 'Note that we have fixed η≥1 earlier at the start of this section as this global assumption is useful later in the paper' is confusing because Theorem 2.1 is then stated and proved for η=0 as well; consider clarifying the scoping of the fixed constants.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":"The paper is a strong technical contribution, and the main gap (β=0) appears local and repairable. I recommend major revision rather than rejection. If the authors fix the degeneracy and re-verify the inequalities, the result would be appropriate for a top venue. The reliance on Theorem 3.15 should be clarified in revision. No concerns about novelty or citation behavior."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nShort version: this is a real result and a serious paper. It gives the first uniform polynomial kernel for pathwidth-η deletion parameterized by vertex cover, with a cubic bound, plus a broader modulator theorem and obstruction-size corollaries. The proofs are explicit, constants are tracked, and the comparison with treewidth deletion is conceptually striking.\n\nWhat is actually new: Giannopoulou et al. showed treewidth-η deletion has no kernel of size O(vc^{(η+1)/2−ε}), so a uniform cubic kernel for pathwidth deletion is a genuine divergence. The main theorem, for modulators to G^β_pw≤η, is substantial; the reduction rules for elimination trees and caterpillars are carefully built, and the minor-output property is used well in the obstruction theorems.\n\nThe soft spots, in order of concern:\n1. The β=0 case is broken as written. Definition 5.12 sets B2 = 2βB1, so for β=0, B2=0 and B#marked = f5.11(B2,1) = 0. Algorithm 3 later applies Lemma 5.11 with c = B#marked = 0, but that lemma requires c ≥ 2. This is not cosmetic: β=0 is exactly the distance-to-pathwidth-1 case advertised in Corollary 1.4(2), and the algorithm would enter the broken ReduceDegreeTree branch whenever a modulator vertex has any neighbor in a pathwidth-1 component. The fix is simple—set B2 := max(1, 2βB1) or treat β=0 separately before degree reduction—but as written, the proof of Main Theorem 1 for β=0 is incomplete.\n2. The reliance on Theorem 3.15 (Bulian-Dawar) for nice constant-depth elimination trees: if the black box returns only approximate distance or a non-nice forest, the sibling/stability arguments in Lemmas 5.14 and 6.3 collapse. This is standard in the area, so I'd call it a caveat rather than a flaw.\n3. Theorem 3.8 cites Bodlaender's treewidth algorithm for pathwidth; the statement is standard, but the citation is imprecise.\n\nI did not verify every case analysis in Lemmas 5.29 and 5.41—they are long—but I found no indication of a deeper failure. The architecture is sound, and the β=0 gap is patchable.\n\nBottom line: this deserves a serious referee. The β=0 bug should be caught and fixed in revision, but it is a minor revision, not a rejection. I would bring it to a reading group.","headline":"Strong uniform kernelization result for pathwidth deletion, but the β=0 case has a patchable gap that must be fixed.","tokens_in":64261,"tokens_out":4753,"would_cite":true,"duration_ms":36515,"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":"Pathwidth-η Deletion admits uniform polynomial kernels on modulator parameterizations where Treewidth-η Deletion provably cannot.","keywords":["kernelization","pathwidth","uniform polynomial kernel","elimination distance","vertex deletion","parameterized complexity","vertex cover parameterization","minor-minimal obstructions"],"falsifier":"Fix β=1 and η=1 and apply the kernel exhaustively to the infinite family of irreducible inputs in $G^1_{\\mathrm{pw}\\le 1}$; if any instance has more than $g(1,1)\\cdot|M|^{60}$ vertices, Main Theorem 1 is false. A more direct test of the load-bearing premise is to search for graphs of elimination distance 1 whose only polynomial-time-computable nice elimination trees have depth growing with the number of vertices, which would destroy the depth-sensitive component bounds.","tokens_in":1983,"feed_emoji":"🧩","tokens_out":3778,"duration_ms":116496,"temperature":0.7,"pith_summary":"Pathwidth-η Deletion asks whether deleting at most k vertices leaves a graph that can be laid out in a sequence of overlapping bags of size at most η+1. This paper establishes that, in kernelization, this problem behaves like Treedepth-η Deletion rather than like Treewidth-η Deletion: for every fixed η and β, the version parameterized by a modulator M whose removal leaves a graph of pathwidth η and elimination distance β to pathwidth-1 graphs admits a uniform polynomial kernel of size $g(\\eta,\\beta)\\cdot|M|^{60}$, meaning the exponent 60 does not depend on η or β. The same machinery yields a cubic kernel in the vertex cover number, a parameterization for which the treewidth analogue is known to have no uniform polynomial kernel. The paper reads this as evidence that Pathwidth-η Deletion may admit a uniform polynomial kernel in the solution size k, placing it on the treedepth side of the treewidth-versus-treedepth divide.","feed_headline":"Pathwidth-η deletion gets a uniform kernel; treewidth cannot","feed_subtitle":"A compression whose exponent is independent of η, with a cubic vertex-cover case.","key_machinery":"The argument is carried by interacting reduction engines. The first is stability in path decompositions: a connected subgraph is stable when every bag that meets it contains exactly the same boundary vertices, and a marking scheme over pairs of modulator neighbors guarantees that one of many similar components of $G-M$ can be deleted safely. The second is polishing sets and near-protrusions, which ensure that any optimal solution touches at most $3(\\eta+1)$ vertices of each remaining low-width piece, together with virtual cliques that make modulator neighbors of a piece behave like a clique without adding edges. The third is a nice $G_{\\mathrm{pw}\\le 1}$-elimination tree of depth at most $\\beta$, whose leaves are caterpillars and whose sibling and ancestor-type structure lets the algorithm identify an irrelevant edge incident to the modulator and delete it. A final protrusion-shrinking step lifts small bags into the modulator and bounds each remaining component by a constant depending only on η and β, yielding the uniform $|M|^{60}$ bound.","core_discovery":"On its own terms, the paper proves that uniform kernelization for Pathwidth-η Deletion is governed by elimination distance to pathwidth-1 graphs rather than by pathwidth alone. Main Theorem 1 gives a kernel on $g(\\eta,\\beta)\\cdot|M|^{60}$ vertices for Pathwidth-η Deletion on the class of graphs of pathwidth at most η with elimination distance at most β to pathwidth-1 graphs, and the kernel outputs an equivalent instance that is a minor of the input, with $k' = k$ whenever the input is a no-instance. The proof fully resolves one of the two bottlenecks, uniformly bounding the number of connected components of $G-M$; it then makes substantial progress on the other by bounding the size of a single component under the bounded-elimination-distance assumption, through degree reductions on modulator vertices and a caterpillar reduction. From this, Corollary 1.5 extracts a cubic kernel in the vertex cover number, and the minor-output property yields polynomial bounds on minor-minimal obstructions to k-apices of pathwidth-η graphs.","pith_inferences":["The cubic vertex-cover kernel suggests the $|M|^{60}$ exponent is far from tight; a refined version of the same marking scheme might yield a uniform kernel with a much smaller fixed exponent.","The route from minor-output kernels to obstruction-size bounds may be a general principle: for any minor-closed class, a uniform kernel parameterized by vertex cover should imply that minor-minimal obstructions to the k-apex class have polynomial size in the vertex cover number.","If Conjecture 1.2 is true but hard, the obstacle is isolated: the components that resist reduction are exactly those with unbounded treedepth and no long paths of degree-2 vertices, so future algorithms or counterexamples can focus on that family."],"forward_implications":["For each fixed η, Pathwidth-η Deletion parameterized by the size of a given vertex cover M has a kernel with $O(vc^3)$ vertices, so the lower bounds that rule out uniform treewidth kernels cannot apply to it.","Uniform polynomial kernels follow for the parameterizations listed in Corollary 1.4, including modulators to bounded-treedepth graphs, distance to pathwidth-1 graphs, distance to graphs of treedepth at most $\\eta+1$, and pathwidth-η graphs without long paths.","Minor-minimal obstructions to the class of k-apices of pathwidth-≤η graphs have size polynomial in their vertex cover number, while the analogous treewidth classes have obstructions whose size depends on η in the exponent.","Because every reduction outputs a minor and keeps k unchanged on no-instances, the kernelization can be applied exhaustively and also serves as a combinatorial size bound for irreducible instances.","If the remaining component-size obstacles are overcome, the same strategy would yield a uniform polynomial kernel parameterized by the solution size k, as Conjecture 1.2 proposes."],"supporting_citations":[{"why":"Supplies the non-uniform polynomial kernel for planar-F deletion and the modulator-based framework that the paper aims to make uniform.","marker":"[31]"},{"why":"Gives the Treewidth-η Deletion lower bound that the paper contrasts, and the uniform treedepth kernel whose techniques are adapted.","marker":"[33]"},{"why":"Defines elimination distance and provides the polynomial-time algorithm for nice elimination trees that Theorem 3.15 relies on.","marker":"[14]"},{"why":"Provides the linear-time pathwidth computation used throughout to obtain path decompositions of the low-width parts.","marker":"[5]"},{"why":"Contains the simplicial-component reduction rule that the component-count reduction of Theorem 2.1 generalizes.","marker":"[7]"},{"why":"Provides the constant-factor approximation for Pathwidth-η Deletion used to convert solution-size parameterization into modulator parameterization.","marker":"[34]"},{"why":"Provides the minor-testing and disjoint-paths machinery used to justify structural arguments and to compute elimination trees.","marker":"[54]"},{"why":"Establishes that pathwidth-1 graphs are exactly caterpillar forests, the structure of the leaf bags used in the caterpillar reduction.","marker":"[12]"},{"why":"Provides the definitions of k-apices and minor-minimal obstructions used in the graph-theoretic consequences.","marker":"[57]"}],"fun_headline_variants":["Uniform kernel for pathwidth deletion, diverging from treewidth","Pathwidth deletion: a uniform kernel where treewidth fails","Pathwidth-η deletion gets uniform kernel; cubic for vertex cover","Pathwidth-η deletion: uniform kernel despite treewidth's lower bound"],"cache_read_input_tokens":66304,"weakest_assumption_plain":"Every depth-sensitive bound in the proof assumes that, for constant β, a nice $G_{\\mathrm{pw}\\le 1}$-elimination tree of depth at most β can be computed in polynomial time; if the cited algorithm returns only approximate elimination distance or a forest whose node subtrees are not connected, the sibling-and-stability arguments collapse.","fun_headline_variants_meta":{"raw":{"variants":["Uniform kernel for pathwidth deletion, diverging from treewidth","Pathwidth deletion: a uniform kernel where treewidth fails","Pathwidth-η deletion gets uniform kernel; cubic for vertex cover","Pathwidth-η deletion: uniform kernel despite treewidth's lower bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000863,"raw_usage":{"total_tokens":3896,"prompt_tokens":1251,"completion_tokens":2645,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":867,"completion_tokens_details":{"reasoning_tokens":2572}},"tokens_in":867,"tokens_out":2645,"duration_ms":17774,"temperature":1.0,"reasoning_tokens":2572,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T10:31:43.543079+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix β=1 and η=1 and apply the kernel exhaustively to the infinite family of irreducible inputs in $G^1_{\\mathrm{pw}\\le 1}$; if any instance has more than $g(1,1)\\cdot|M|^{60}$ vertices, Main Theorem 1 is false. A more direct test of the load-bearing premise is to search for graphs of elimination distance 1 whose only polynomial-time-computable nice elimination trees have depth growing with the number of vertices, which would destroy the depth-sensitive component bounds.","supporting_citations":[{"cited_title":"37 Eva-Maria C","cited_arxiv_id":null,"evidence_quote":"Establishes that pathwidth-1 graphs are exactly caterpillar forests, the structure of the leaf bags used in the caterpillar reduction."}],"review_version":1}