{"id":"afade5c7-5ae4-4364-bdff-58815ec1d0b9","arxiv_id":"2607.26638","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Rooted tree minors satisfy a linear Erdős-Pósa bound: k vertex-disjoint rooted models or a hitting set of O(k) vertices.","lead":"The paper proves a rooted version of the Erdős-Pósa property for tree minors: any graph either contains many vertex-disjoint rooted copies of a fixed tree, or a linear-size set of vertices destroys all such copies. This generalizes Gallai's classical S-path theorem and improves the previous quadratic bound to a linear one.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: proof is internally coherent; main external black-box (Thm 3) is standard and plausibly correct.","rationale":"The reader's verdict of ACCEPT with moderate confidence is well supported. I examined the main inductive proof of Theorem 11, the construction of C_t, Lemma 9's packing argument, and the applications of the external theorems. The proof is internally consistent; the cited Theorem 3 is the weakest point because it is load-bearing and not re-proved, but it is a plausible and standard result. The minor textual errors do not threaten the main theorem. Since no actual flaw was identified, the verdict should remain unchanged, though an independent check of Theorem 3 would further de-risk the dependency.","tokens_in":20654,"tokens_out":41449,"duration_ms":386066,"concrete_test":"Independently verify Theorem 3 by brute force for all graphs on at most 7 vertices and all subsets S, for every tree F on at most 4 vertices: compute pw(G,S) by enumerating path decompositions and check that pw(G,S) ≤ 2|V(F)|−2 whenever G has no S-rooted model of F. If a counterexample is found, the main proof needs a replacement tool; if none appears, the black-box assumption is further corroborated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After close reading, I find no internal flaw that threatens the central claim. The induction in Theorem 11 is intricate but each step checks out: Lemma 5 gives the required structural properties of C_t, Lemma 6 correctly converts large pathwidth into a C_t-member via Theorem 3, Lemma 9 provides the needed linear packing/covering for K3 and rooted K1,3, and Claim 14's use of Lemma 8 is valid because the removed rooted subtree leaves a single component, justifying the c'=1 bound. The only genuinely load-bearing dependency is the cited Theorem 3 (Hodor et al. Theorem 7): if no S-rooted model of a forest F, then pw(G,S) ≤ 2|V(F)|−2. This is used directly in Lemma 6 and again in Theorem 2, and it is not re-proved here. However, this is a standard type of excluded-minor/pathwidth bound, and I have no reason to doubt it. Minor typos (e.g., the 'M1' slip in Lemma 5(b) and some numerical subscripts in Section 3) do not affect the argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves Theorem 1: for every t-vertex tree T there is a function g(t) such that for every graph G, every S⊆V(G), and every k, either G contains k vertex-disjoint S-rooted models of T, or there is a set X of at most g(t)k vertices hitting all S-rooted models of T. This improves the earlier O(k^2) bound of Hodor, La, Micek, and Rambaud and generalizes Gallai's S-path theorem. The main device is a hierarchy C_t(G,S) of subgraphs; Theorem 11 gives a linear packing/covering statement for C_t by induction on t. The proof uses two external results from [9]: the rooted pathwidth bound of Theorem 3 and the bounded-treewidth hitting lemma of Lemma 4. The paper also derives Theorem 2 for forests with partially rooted models and gives improved bounds for paths (quadratic) and stars (linear).","tokens_in":20940,"tokens_out":25137,"duration_ms":257215,"significance":"If correct, this is a substantial advance: rooted tree minors inherit the linear Erdős–Pósa behavior known for unrooted tree minors, and the proof is genuinely different from the two earlier unrooted proofs [5,7]. The auxiliary packing/covering lemma for rooted K3 and rooted K1,3 (Lemma 9) and the (F,R)-model generalization are useful in their own right. The induction in Theorem 11 is intricate but internally coherent, and the explicit recurrence for h(t) is a strength. The main caveat is the black-box use of Theorem 3 from [9]; it is a standard excluded-minor/pathwidth theorem and not circular with the target result, but the proof would collapse if that theorem failed. I found no internal flaw threatening the central claim.","major_comments":[],"minor_comments":[{"comment":"In Case (C2), the text says 'the union of M1, M2 with the new branch set B'. The subgraph M1 is never defined; the intended sentence appears to be 'the union of M2 and M3 with the new branch set B'. Please correct this typo.","section":"Section 2, Lemma 5(b)"},{"comment":"The proof ends with 'A straightforward induction on t then shows that C_t(G,S)≠∅'. Since Lemma 6 is used in Lemma 7 and again in the proof of Theorem 1, this step is load-bearing. Please spell out the induction, in particular how an S-rooted model of the complete ternary tree of height t yields an element of C_t(G,S), and how the two cases (C1)/(C2) in the definition of C_t arise. I believe the statement is true, but the one-line proof is too terse.","section":"Section 3, Lemma 6"},{"comment":"As written, the family H={G[V(P_a)∪V(Q)] : Q∈Q_j, a∈[i(j),i(j+1)-1]} does not have the asserted pairwise-intersection property: two members corresponding to different paths Q are vertex-disjoint because the Q_j paths are pairwise disjoint. The intended family appears to be {G[V(Q)∪⋃_{a∈[i(j),i(j+1)-1]}V(P_a)] : Q∈Q_j}. Please correct the display and the sentence 'these subgraphs pairwise intersect'.","section":"Section 3, Claim 15"},{"comment":"The line 'there is a set X1⊆V(G−Z0)' should read 'X1⊆V(G−X0)'.","section":"Section 4, proof of Theorem 2"},{"comment":"There are several small typos: 'at least one the following' before Theorem 11, 'G−Xhas notS-rooted ofK_{1,ℓ}' in Theorem 24, and 'Erdős-Pósa proper ty' in the header. A careful proofreading pass would be worthwhile.","section":"Throughout"}],"recommendation":"minor_revision","confidential_remarks":"The main dependency is the black-box Theorem 3 from [9], a paper co-authored by one of the authors. This is a legitimate external theorem and not circular, but it concentrates risk. Claim 15 is formally wrong as written; the intended correction is immediate, but it should be fixed before publication. No deeper internal issue was found."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline: this is the real thing. The authors prove a linear Erdős-Pósa bound for S-rooted tree minors, improving the O(k^2) bound from Hodor et al., and I went through the proof looking for a load-bearing hole and didn't find one. The main induction (Theorem 11) is intricate but coherent: Lemma 5 gives the structural properties of the C_t hierarchy, Lemma 6 converts large pathwidth into a C_t-member via Theorem 3, and Claim 14's use of Lemma 8 works. The result is genuinely new — the earlier rooted result was quadratic, and the recursive C_t hierarchy plus induction on t is not a routine adaptation of the unrooted proofs. I also like that they handle partially rooted forests, which is a real generalization, and the path/star sections give cleaner constants.\n\nSoft spots: the paper leans on two results from [9], a paper co-authored by Rambaud: Theorem 3 (excluded forest / pathwidth) and Lemma 4. The pathwidth theorem is load-bearing in Lemma 6 and in the proof of Theorem 2. It is structurally different from the Erdős-Pósa theorem being proved, so the circularity concern is minor, but because the cited paper shares an author, a referee should re-verify that theorem. The stress-test note says it is standard and plausible; I agree. There are a few terse spots — Lemma 6's 'straightforward induction' and the bramble/interval argument in Claim 15 could be spelled out more — and Lemma 5(b) has an apparent typo ('union of M1, M2' vs M2/M3). None of these touches the central claim.\n\nVerdict: this deserves serious peer review. The proof is honest, detailed, and the main dependency is a standard pathwidth bound rather than the target result. The paper is for graph minor people working on Erdős-Pósa; they'll want to check Theorem 3 and the induction, but the result should stand. I'd cite it.","headline":"Linear Erdős-Pósa for rooted tree minors is real and the proof holds up; the main dependency is a standard pathwidth black box, not the result itself.","tokens_in":21414,"tokens_out":2228,"would_cite":true,"duration_ms":23042,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C83","05C70","05C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Rooted tree minors satisfy a linear Erdős–Pósa property","keywords":["rooted tree minors","Erdős–Pósa property","tree minors","pathwidth","S-paths","vertex-disjoint packing","hitting set","forests"],"falsifier":"Compute pw(G,S) for small graphs with no S-rooted model of a 4-vertex path: the theorem says every such instance has pw(G,S) ≤ 6, so a single example with pathwidth 7 or more disproves the black-box theorem on which the proof rests. For the theorem itself, exhaustive search over small graphs for t=2,3 and k=2,3 can test the claimed dichotomy with the paper's explicit g(t) values.","tokens_in":20569,"feed_emoji":"🌳","tokens_out":6859,"duration_ms":69025,"temperature":0.7,"pith_summary":"The paper proves that rooted tree minors obey the Erdős–Pósa property with a bound linear in k. Given any fixed t-vertex tree T, any graph G, and any root set S, either G contains k vertex-disjoint subgraphs each having an S-rooted model of T, or a set of at most g(t)k vertices meets every such model. This generalizes the classical S-path theorem, which is the case T=K2, and improves a previously known quadratic bound. The result also extends to forests with partially rooted branch sets, and the paper shows improved bounds for paths and stars.","feed_headline":"Rooted tree minors get a linear Erdős–Pósa bound","feed_subtitle":"In any graph, either k vertex-disjoint rooted copies of a fixed tree pack in, or g(t)·k vertices hit every one.","key_machinery":"The engine is the family C_t(G,S): C_0 consists of single vertices of S, and each larger level joins three vertex-disjoint members of C_{t-1} by three paths in one of two configurations. Lemma 5 proves every member of C_t contains an S-rooted model of every t-vertex tree, so packing or hitting C_t is equivalent to the root-minor problem. Two supporting results carry the linear constant: a rooted Erdős–Pósa statement for the basic trees K3 and K1,3 (Lemma 9), and a pathwidth lemma that guarantees C_t is nonempty once pw(G,S) is large, using an excluded-rooted-forest pathwidth bound. The recursion in t then yields the linear function h(t).","core_discovery":"The central discovery is that adding rootedness does not spoil the linear Erdős–Pósa behaviour of tree minors: for every t there is a number g(t) such that, in every graph G with a distinguished set S, the family of S-rooted models of T is either large enough to pack k disjoint copies or small enough to be destroyed by g(t)k vertices. The bound on the hitting-set size is best possible as a function of k. The proof constructs a nested family C_t(G,S) of subgraphs that force rooted models of all t-vertex trees and shows recursively that either k disjoint members can be found or a hitting set of size h(t)k exists. A separate argument converts this into the theorem, and then into the forest gene","pith_inferences":["Because the proof's engine treats pathwidth as the obstruction, the C_t hierarchy may yield a practical approximation algorithm for rooted pathwidth: one could try to find k disjoint members or an approximate hitting set without computing an optimal decomposition.","The unrooted case S=V(G) gets a proof distinct from the two earlier linear proofs; this new machinery might be adapted to recover the optimal unrooted bound t(k−1) without the earlier separation-based arguments.","The conjecture that |V(F)|(k−1) suffices for every forest and root-requirement pair is the natural next test; the path and star results are consistency checks but do not reach the general bound.","Since the proof leans on a single externally supplied pathwidth theorem, replacing that black box by a self-contained proof — or finding a counterexample — would either strengthen the paper's independence or reveal a limitation. This is an editorial observation, not a paper claim."],"forward_implications":["For every fixed tree T, the rooted Erdős–Pósa function is linear in k, so the qualitative behaviour matches the unrooted tree-minor theorem.","The classical S-path theorem (T=K2) follows as a special case, giving an alternative route to Gallai's packing–covering theorem for S-paths.","The earlier quadratic bound for rooted tree minors is superseded by a linear one.","The partially rooted forest version supplies the same linear guarantee when only some branch sets need roots, interpolating between rooted and unrooted models.","For paths the bound is improved to (ℓ²−1)(k−1) and for stars to 21ℓ(k−1), both independent of the general fast-growing g(t)."],"fun_headline_variants":["Rooted tree minors keep linear Erdős–Pósa bound","Linear hitting set for rooted tree minors","Rooted tree minors: linear Erdős–Pósa, best possible","Generalizing Gallai's S-path theorem to trees","Packing vs hitting rooted tree minors linearly"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is the previously proved excluded-forest pathwidth theorem — if a graph has no S-rooted model of a forest F then pw(G,S) ≤ 2|V(F)|−2 — which is invoked without proof; should it fail, the main proof loses its engine.","fun_headline_variants_meta":{"raw":{"variants":["Rooted tree minors keep linear Erdős–Pósa bound","Linear hitting set for rooted tree minors","Rooted tree minors: linear Erdős–Pósa, best possible","Generalizing Gallai's S-path theorem to trees","Packing vs hitting rooted tree minors linearly"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000162,"raw_usage":{"total_tokens":1106,"prompt_tokens":806,"completion_tokens":300,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":550,"completion_tokens_details":{"reasoning_tokens":221}},"tokens_in":550,"tokens_out":300,"duration_ms":3939,"temperature":1.0,"reasoning_tokens":221,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T11:47:51.297344+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute pw(G,S) for small graphs with no S-rooted model of a 4-vertex path: the theorem says every such instance has pw(G,S) ≤ 6, so a single example with pathwidth 7 or more disproves the black-box theorem on which the proof rests. For the theorem itself, exhaustive search over small graphs for t=2,3 and k=2,3 can test the claimed dichotomy with the paper's explicit g(t) values.","supporting_citations":[],"review_version":1}