{"id":"25e98cfe-3365-4f02-a5f1-f415d70648a5","arxiv_id":"2501.13907","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"In S_{t,t,t}-free graphs, deleting the closed neighborhoods of at most 3t+11 vertices yields a rigid extended strip decomposition whose particles each have at most half the total weight.","lead":"This paper proves that in graphs with no long claws, deleting the neighborhoods of a constant number of vertices splits the graph into small pieces. The result sharpens a previous logarithmic bound and simplifies algorithms for Maximum Weight Independent Set.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader's verdict of ACCEPT with moderate confidence is well calibrated. I checked the paper's most delicate steps rather than relying on the abstract or theorem statements. Lemma 10, the reader's identified weakest assumption, is correctly proved and is indeed essential: it controls how an induced path between peripheral vertices can cross an extended strip decomposition, and it is used in Claim 12 to force the big full-edge particle to be disjoint from Q1 and later to bound X by 4. The potential subtlety in Claim 12 — that Corollary 11 might only yield a single vertex in one interface — is resolved by observing that a singleton intersection with an edge particle is impossible for an induced path between two distinct peripheral vertices; the second step of the path would create a chord with the endpoint or violate the interface bound. Claim 13's step from 'C not contained in any component of G − N[V(Q)]' to the existence of a Q-vertex q outside N[S] adjacent to C is terse, but it is valid: if C met N[V(Q)] only through vertices of Q2 or z', those vertices lie in S, contradicting C ⊆ V(G − N[S]); hence the witness lies in Q1 and also in X, giving the stated contradiction. Lemma 8's transformation from a relaxed to a proper rigid extended strip decomposition is lengthy but each operation strictly decreases a well-founded measure and preserves the weight bound; the polynomial-time claim is credible. The independent result by Chudnovsky et al. adds external plausibility but does not substitute for checking this proof. Minor exposition issues — the inaccurate sentence about N_G[V(Q)] ∩ η(p) and the compressed wording in Claim 13 — do not affect the validity of the argument and can be repaired without changing the bound or the algorithm. No load-bearing concern survives scrutiny, so the reader's ACCEPT verdict is unchanged.","tokens_in":16519,"tokens_out":45468,"duration_ms":395463,"concrete_test":"Independently re-derive Claim 12 without relying on the ambiguous 'endpoints' phrasing of Corollary 11: prove directly that an induced path between two distinct peripheral vertices meeting η(pq) must contain at least one vertex in each of η(pq,p) and η(pq,q), and that a singleton intersection is impossible. If this direct proof fails, the bound |X| ≤ 4 and Claim 13 collapse.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. I read the full proof of Theorem 3 in good faith and the central argument holds together. Lemma 10 (Section 3.2) is genuinely load-bearing, but its proof is sound: the auxiliary crossing claim forces the two vertices on opposite sides of a vertex particle to lie in the same interface, and the final contradiction from a vertex entering the same edge interface twice is valid. Claim 12's use of Corollary 11 is also justified: an induced path between two distinct peripheral vertices cannot have a singleton intersection with an edge particle. If the singleton were interior, the two neighboring path vertices would lie in interfaces that are complete to each other, creating a chord; if it were an endpoint, the path could not continue past the first edge without creating a chord with that endpoint. Thus Corollary 11 really does give one endpoint in each side of the edge. Claim 13 checks out as well: a Q-vertex adjacent to the big component C and outside N[S] must lie in Q1, because Q2 ∪ {z'} is entirely contained in S. The only weaknesses are expositional, not logical: the sentence claiming N_G[V(Q)] ∩ η(p) = ∅ for isolated p is false in general (z' may be adjacent to η(p)), but the needed conclusion still follows because any neighbor of η(p) outside η(p) lies in N_G[V(Q)] and is removed; and the inference in Claim 13 about C not being contained in a component is terse but can be made rigorous. These do not threaten the theorem.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves Theorem 3: for every fixed integer t ≥ 1, given a vertex-weighted graph G and an integer t, one can in polynomial time either find an induced copy of the long claw S_{t,t,t} or output a set S of at most 3t+11 vertices such that G − N[S] admits a rigid extended strip decomposition in which every particle has weight at most half the total weight of V(G). This improves the O(log n) bound from Majewski et al. [22] to a constant, and the authors argue that this removes a logarithmic factor in the exponent of the quasipolynomial-time MWIS algorithm for S_{t,t,t}-free graphs and simplifies the polynomial-time algorithms of [3]. The proof refines the Gyárfás-path argument, uses the three-in-a-tree theorem (Theorem 5), and relies on a structural lemma (Lemma 10) about induced paths between peripheral vertices in extended strip decompositions.","tokens_in":16732,"tokens_out":48677,"duration_ms":399719,"significance":"If correct, the result is a clean and useful structural improvement: it turns a logarithmic number of deleted neighborhoods into a constant number, which is the right order of magnitude for this type of separator statement. The proof is largely self-contained modulo the Gyárfás path theorem and the three-in-a-tree theorem, and it gives an explicit constant 3t+11 and a polynomial-time algorithm. The paper also honestly mentions the independent related work [9]. The main concern is a gap in the treatment of isolated vertex particles in the extended strip decomposition; this does not appear to threaten the truth of the theorem, but it is load-bearing in the written proof and needs to be repaired before the paper can be accepted.","major_comments":[{"comment":"The claim \"Since Q is a path between peripheral vertices then N_G[V(Q)] ∩ η(p) = ∅\" is not correct as stated. The Gyárfás path Q has endpoints x and ℓ, and ℓ is not peripheral in the extended strip decomposition (H,η) of (G′, {x,y,z}); moreover, the vertex z′ ∈ V(Q) is not present in G′ and may be adjacent to η(p) in G. Consequently the conclusion w(η(p)) ≤ w(V)/2 is not established. This conclusion is used to justify the reduction \"Since every nontrivial particle is contained in a full edge particle we can assume without loss of generality that A is a full edge particle.\" Without this reduction, the proof does not cover the case where the heavy particle is an isolated vertex particle, and the subsequent Claims 12 and 13 as well as the final bound |S| ≤ 3t+11 all rely on A being a full edge particle. The gap seems repairable by a direct argument for isolated vertex particles (all their neighbors in G lie in N[Y ∪ {z′}], so after removing those neighborhoods the Gyárfás property can be applied), but the current text does not supply that argument.","section":"Section 3.2, proof of Theorem 3, paragraph beginning \"Suppose now that there exists a particle A...\""},{"comment":"The WLOG assumption that for every isolated p ∈ V(H) the set G[η(p)] is connected is stated without proof. The intended justification is presumably that one may split p into several isolated vertices, one for each connected component of G[η(p)], which preserves all extended strip decomposition properties and rigidity. This should be stated explicitly, because the subsequent weight bound w(η(p)) ≤ w(V)/2 depends on η(p) being a single connected component of G − N[V(Q)].","section":"Section 3.2, proof of Theorem 3, same paragraph"}],"minor_comments":[{"comment":"The expression \"x_i x_{j′} ∈ E(H)\" should be \"x_i x_{j′} ∈ E(G)\"; the edge is in the original graph, not in H.","section":"Lemma 10, last line of the proof"},{"comment":"The inference \"η(pq,p) ≠ {z} and η(pq,q) ≠ {z} so z ∉ η(pq)\" is terse. The missing justification is that if z were in η(pq), then since z is peripheral, one of the two interfaces would be exactly {z}; this would contradict the existence of the endpoint v_p ∈ V(Q1) ∩ η(pq,p) from Corollary 11, because z ∉ V(Q1).","section":"Corollary 11, proof"},{"comment":"The sentence \"Since Q is a path between peripheral vertices\" appears to be a typo. The path Q itself does not have two peripheral endpoints in (H,η); only Q1 (between x and y) and Q2 (starting at z) have peripheral endpoints. Please rephrase to avoid ambiguity.","section":"Section 3.2, proof of Theorem 3, paragraph before Claim 12"},{"comment":"When defining X = N_{G′}[A] ∩ V(Q1), the proof says that if three vertices of Q1 lie in three distinct interfaces incident to the same endpoint of pq, then they form a triangle. This is correct by property 2 of Definition 4, but the connection to the induced path Q1 should be made explicit, as a path cannot contain a triangle.","section":"Section 3.2, proof of Theorem 3, after Claim 12"}],"recommendation":"major_revision","confidential_remarks":"The paper is a genuine improvement over [22] and the main theorem is very plausible. The reader's report and the stress-test note both lean toward acceptance, but on close reading the proof has a specific gap: the reduction to a full-edge-particle heavy case relies on a claim about isolated vertex particles that is false as written. The gap is local and appears fixable without changing the structure of the argument, so I recommend major revision rather than rejection. The independent result [9] is acknowledged, and the overlap with [22] is not problematic because the theorem here is not assumed. The exposition otherwise is careful and the constant 3t+11 is explicit."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is a genuine improvement over [22]: instead of deleting neighborhoods of O(log n) induced paths, they get a set S of at most 3t+11 vertices such that G-N[S] admits a rigid extended strip decomposition with all particles of weight at most w(V)/2. It directly answers an open question from [22], and the proof is much more than a cosmetic tweak—the refined terminal selection and the analysis of the big particle/interface interaction are real new work. The paper also honestly notes the independent similar result [9], which is good practice.\n\nI read the proof in good faith and traced the key steps. The load-bearing Lemma 10, which forces induced paths between peripheral vertices to lie in edge particles with at most one vertex per interface, is intricate but correct. The stress-test note is accurate: Claim 12's use of Corollary 11 checks out, and Claim 13's contradiction goes through once you unpack the terser inference. The only soft spots are expositional. The WLOG that isolated vertex particles induce connected subgraphs is stated without proof, and the accompanying sentence claiming N_G[V(Q)] ∩ η(p) = ∅ is actually false in general—z' may be adjacent to η(p). But the needed conclusion still holds because any such neighbor is removed when we delete N[Y ∪ {z'}] anyway, so this is fixable without changing the theorem. Lemma 8's conversion to a rigid decomposition is also dense and would benefit from a fuller walkthrough.\n\nThe proof rests on two external results, the Gyárfás path and the three-in-a-tree theorem, and is not circular: despite two shared authors with [22], they never assume the theorem they are improving. No parameters are fitted; this is a clean structural result.\n\nWho is this for? Researchers working on MWIS in H-free graphs and on extended strip decompositions. It simplifies the bounded-degree polynomial algorithm and removes one logarithmic factor from the quasipolynomial algorithms, though it does not by itself resolve polynomiality.\n\nNot a fatal flaw anywhere. The main limitation is that the proof is long and intricate, so a referee will need patience, but it deserves a serious referee and, after minor revisions addressing the WLOG and the false sentence, should be accepted.","headline":"Constant-size separator for S_{t,t,t}-free graphs replaces O(log n) paths; proof is sound, with minor expositional fixes needed.","tokens_in":17329,"tokens_out":1117,"would_cite":true,"duration_ms":11943,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C69","05C85","05C75","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that in any graph with no induced long claw $S_{t,t,t}$, one can in polynomial time either find such a claw or delete the neighborhoods of at most $3t+11$ vertices so that the remainder admits a rigid extended strip…","keywords":["S_{t,t,t}-free graphs","long claws","Gyárfás path argument","extended strip decomposition","Maximum Weight Independent Set","three-in-a-tree","constant-size separator"],"falsifier":"Find a graph $G$ with an extended strip decomposition $(H,\\eta)$ and an induced path $Q$ between two peripheral vertices such that $Q$ uses a vertex outside $\\bigcup_{e\\in E(H)}\\eta(e)$ or has two vertices in $\\eta(e,a)$ for some edge $e=ab$; Lemma 10 forbids both, and the proof of Theorem 3 would collapse.","tokens_in":16289,"feed_emoji":"🌳","tokens_out":10745,"duration_ms":77582,"temperature":0.7,"pith_summary":"This paper proves that the Gyárfás path argument for graphs with no long claw $S_{t,t,t}$ can be sharpened from a logarithmic to a constant number of vertex deletions. The main theorem gives a polynomial-time procedure that, for any fixed $t$, either outputs an induced copy of $S_{t,t,t}$ or finds a set $S$ of at most $3t+11$ vertices such that $G-N[S]$ admits a rigid extended strip decomposition whose every particle has weight at most $w(V)/2$. Because particles behave like connected components for the Maximum Weight Independent Set problem, this reduces the recursive divide-and-conquer overhead in algorithms for $S_{t,t,t}$-free graphs: it removes one logarithmic factor from the exponent of the known quasipolynomial algorithm and makes polynomial-time algorithms for bounded-degree and sparse cases immediate. The improvement comes from inspecting the last two vertices of a minimal Gyárfás path and controlling the interaction between the big component and the big particle of the returned decomposition.","feed_headline":"Deleting 3t+11 neighborhoods splits long-claw-free graphs","feed_subtitle":"A constant-size separator replaces O(log n) in the Gyárfás path argument, enabling simpler MWIS algorithms.","key_machinery":"The central objects are the extended strip decomposition (ESD), a partition of the graph into particles attached to vertices, edges, and triangles of an auxiliary graph $H$ that generalizes connected components, and the Gyárfás path $Q$, a minimal induced path whose closed-neighbourhood removal leaves only connected components of weight at most half. The argument is carried by three lemmas: Lemma 7 bounds the neighbourhood of a full-edge particle by neighbourhoods of two of its vertices; Lemma 10 forces any induced path between peripheral vertices of an ESD to lie in the union of edge particles and to meet each interface in at most one vertex; and Lemma 8 rigidifies a refined ESD without increasing particle weight, at the cost of possibly returning a two-vertex set whose neighbourhood removal splits the graph. The three-in-a-tree theorem supplies the ESD or the induced claw, and the final bound $|S|\\le 3t+11$ comes from counting the selected vertices: $3t+3$ from the three subpaths, at most $4$ from the path–particle interface, at most $2$ from Lemma 7, plus $\\ell$ and $z'$.","core_discovery":"The paper's central claim is Theorem 3: given a graph $G=(V,E)$ with nonnegative vertex weights and an integer $t\\ge 1$, one can in polynomial time either output an induced copy of $S_{t,t,t}$ or output a set $S$ with $|S|\\le 3t+11$ and a rigid extended strip decomposition of $G-N[S]$ in which every particle has weight at most $w(V)/2$. This improves the earlier result [22], which required $O(\\log n)$ induced paths and hence $O(\\log n)$ neighborhoods. The proof runs a minimal Gyárfás path $Q$; if $Q$ is short it is taken as $S$, otherwise it selects three vertices $x,y,z$ on $Q$ at prescribed distances, deletes neighborhoods of three $t$-vertex subpaths, and invokes the three-in-a-tree theorem to obtain either an induced $S_{t,t,t}$ or an extended strip decomposition of the remaining graph. A structural lemma (Lemma 10) — induced paths between peripheral vertices stay inside edge particles and meet each interface at most once — is used to show that a big particle can be separated from the rest by at most four vertices from $Q$, two further vertices, and the last vertex $\\ell$ and its predecessor $z'$, giving the constant bound.","pith_inferences":["The technique suggests that the three-in-a-tree black box may be avoidable in this context; a purely combinatorial argument bounding the interface between a Gyárfás path and an ESD could reduce the additive constant and the dependence on $t$.","The same last-two-vertices observation might extend to subdivided claws $S_{a,b,c}$ with unequal path lengths, giving constant-size separators for broader hereditary classes where the three-in-a-tree output is still an ESD.","Because the separator size is independent of $n$, the result hints that $S_{t,t,t}$-free graphs have bounded tree-independence number after deleting a constant number of neighborhoods, which if true would connect to other decomposition-based algorithms."],"forward_implications":["For fixed $t$, the polynomial-time algorithm for Maximum Weight Independent Set in $S_{t,t,t}$-free graphs of bounded degree follows immediately from Theorem 3: branch on $N[S]$, recurse on the particles of the ESD.","The algorithm for $S_{t,t,t}$-free graphs that exclude a fixed biclique $K_{s,s}$ as a subgraph can be simplified, since the constant-size separator replaces the logarithmic one.","Using Theorem 3 inside the quasipolynomial-time algorithm for $S_{t,t,t}$-free graphs removes one logarithmic factor from the running-time exponent.","The structural statement holds for every fixed $t$ with a polynomial-time algorithm, so the separator size $3t+11$ depends only on $t$, not on $n$."],"supporting_citations":[{"why":"Supplies the previous $O(\\log n)$ analog of the Gyárfás path argument and the extended strip decomposition framework that this paper refines.","marker":"[22]"},{"why":"Provides the three-in-a-tree theorem that returns either an induced tree (hence an $S_{t,t,t}$) or a rigid extended strip decomposition with prescribed peripheral vertices.","marker":"[12]"},{"why":"Gives the near-linear implementation of three-in-a-tree used to keep the overall algorithm polynomial.","marker":"[20]"},{"why":"States the Gyárfás path theorem (Theorem 1) that supplies the minimal induced path $Q$ used as the starting point of the proof.","marker":"[8]"},{"why":"The quasipolynomial-time Maximum Weight Independent Set algorithm whose analysis uses the prior structural result and which the improvement simplifies.","marker":"[14]"}],"fun_headline_variants":["Constant neighborhoods now split long-claw-free graphs","3t+11 neighborhoods: the new constant bound","From O(log n) to constant: splitting long-claw-free","Deleting 3t+11 neighborhoods separates long-claw-free"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof depends on Lemma 10, which asserts that an induced path between two peripheral vertices of an extended strip decomposition lies entirely inside edge particles and meets each interface in at most one vertex; if that lemma fails, the constant $3t+11$ does not follow from this argument.","fun_headline_variants_meta":{"raw":{"variants":["Constant neighborhoods now split long-claw-free graphs","3t+11 neighborhoods: the new constant bound","From O(log n) to constant: splitting long-claw-free","Deleting 3t+11 neighborhoods separates long-claw-free"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000356,"raw_usage":{"total_tokens":1976,"prompt_tokens":1031,"completion_tokens":945,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":647,"completion_tokens_details":{"reasoning_tokens":876}},"tokens_in":647,"tokens_out":945,"duration_ms":8412,"temperature":1.0,"reasoning_tokens":876,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T15:29:56.713053+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a graph $G$ with an extended strip decomposition $(H,\\eta)$ and an induced path $Q$ between two peripheral vertices such that $Q$ uses a vertex outside $\\bigcup_{e\\in E(H)}\\eta(e)$ or has two vertices in $\\eta(e,a)$ for some edge $e=ab$; Lemma 10 forbids both, and the proof of Theorem 3 would collapse.","supporting_citations":[{"cited_title":"Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás’ Path Argument.The ACM Transactions on Compu- tation Theory, 16(2), mar 2024.doi:10.1145/3636422","cited_arxiv_id":null,"evidence_quote":"Supplies the previous $O(\\log n)$ analog of the Gyárfás path argument and the extended strip decomposition framework that this paper refines."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the three-in-a-tree theorem that returns either an induced tree (hence an $S_{t,t,t}$) or a rigid extended strip decomposition with prescribed peripheral vertices."}],"review_version":1}