Erd\H{o}s-P\'osa property of rooted tree minors

Cl\'ement Rambaud; Eileen Robinson; Gwena\"el Joret; Quentin Claus

Erd\H{o}s-P\'osa property of rooted tree minors

T0 review · 0 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Rooted tree minors satisfy a linear Erdős–Pósa property

desk verdict 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. read the letter →

arxiv 2607.26638 v1 pith:OCDHPIVL submitted 2026-07-29 math.CO cs.DM

Quentin Claus , Gwenaël Joret , Clément Rambaud , Eileen Robinson This is my paper · ORCID

classification math.COcs.DM MSC 05C8305C7005C05

keywords rootedtreeminorsErdős–PósapropertypathwidthS-pathsvertex-disjointpackinghittingsetforests

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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).

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

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).

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

Soft 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.

Verdict: 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.

Referee Report

0 major / 5 minor

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).

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.

minor comments (5)

[Section 2, Lemma 5(b)] 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 3, Lemma 6] 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 3, Claim 15] 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 4, proof of Theorem 2] The line 'there is a set X1⊆V(G−Z0)' should read 'X1⊆V(G−X0)'.
[Throughout] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main induction is genuinely self-contained; the cited results from [9] are structural pathwidth/treewidth lemmas that do not assume the target Erdős–Pósa bound.

full rationale

The proof of Theorem 1 proceeds through Theorem 11, an induction on t about the recursively defined classes C_t(G,S). Every ingredient in that induction is either proved in the paper (Lemma 5, Lemma 8, Lemma 9, Lemma 19, Claim 14, etc.) or is a standard black box: Theorem 3 from [9] says that a graph with no S-rooted model of a forest F has pw(G,S) ≤ 2|V(F)|−2, and Lemma 4 from [9] is a bounded-treewidth packing/covering statement. Neither of these is the linear Erdős–Pósa bound being proved; Theorem 3 has no k parameter and no separator-size conclusion, and Lemma 4 only applies under a treewidth bound tw(G,S)<w. Although [9] shares an author with this paper, the assumptions of these cited results do not include the target result, so under the review rules they are real evidence rather than circularity. Lemma 6 merely converts the external pathwidth bound into existence of a C_t member; Lemma 5 is proved in full; Lemma 9 is an explicit proof of the rooted K3/K1,3 base case. No fitted parameters are renamed as predictions, no uniqueness theorem is imported, and no step is equal by construction to its input. Therefore the derivation chain is self-contained (modulo independent published lemmas), and there is no circular step.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No numerical parameters are fitted; all constants arise from the proof. The central derivation rests on two prior theorems from [9] (pathwidth bound and rooted treewidth packing-covering lemma), plus Diestel's path-width lemma. These are load-bearing but do not include the target linear Erdős-Pósa result. No new physical or mathematical entities are postulated.

assumptions (5)

domain assumption Hodor et al. Theorem 7: if G has no S-rooted model of forest F then pw(G,S) ≤ 2|V(F)|−2
Invoked as Theorem 3; used in Lemma 6 and in the proof of Theorem 2. Self-cited from [9], but independent of the linear Erdős-Pósa claim.
domain assumption Corollary of Hodor et al. Lemma 23: if tw(G,S)<w and G has no k vertex-disjoint S-rooted models of a connected H, then a set of at most w(k−1) vertices hits every such model
Used as Lemma 4 to convert bounded pathwidth into a linear hitting set for S-rooted T-models.
domain assumption Diestel's path-width lemma: large pathwidth yields a separation with a rooted tree model on one side
Used through Lemma 18 to support Lemma 19 in the proof of Theorem 2.
standard math Menger's theorem
Used repeatedly: Lemma 9, Claim 14, Theorem 21, and Theorem 24.
standard math Helly property of intervals
Used in Lemma 7 and Theorem 11 to obtain small transversals of interval families and brambles.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Erd\H{o}s-P\'osa property of rooted tree minors." pith.science (2026). https://pith.science/paper/OCDHPIVL

@misc{pith2026260726638,
  author       = {Pith},
  title        = {Pith review of: Erd\Hos-P\'osa property of rooted tree minors},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OCDHPIVL}},
  note         = {Machine review of arXiv:2607.26638}
}

abstract

Fiorini, Joret, and Wood (2013) showed that tree minors satisfy the so-called Erd\H{o}s-P\'osa property with a linear bound: For every tree $T$ there exists a constant $c \geq 1$ such that, for every graph $G$ and integer $k\geq 0$, either $G$ contains $k$ vertex-disjoint subgraphs each containing a $T$-minor, or $G$ has a set $X$ of at most $c k$ vertices such that $G-X$ has no $T$-minor. In this paper, we prove that the same result remains true if, given a subset $S$ of vertices of $G$, one only considers $T$-minors of $G$ that are rooted in $S$. Here, a $T$-minor is rooted in $S$ if there is a minor-model of $T$ where each branch set contains a vertex from $S$. This result can be seen as a generalization of the classical $S$-Path Theorem of Gallai, which corresponds to the case $T=K_2$. The upper bound on the size of $X$ is best possible up to the value of the constant $c$, and improves on an earlier $O(k^2)$ bound due to Hodor, La, Micek, and Rambaud (2026).

Figures

Figures reproduced from arXiv: 2607.26638 by the authors.

**Figure 1.** The two cases (C1) (on the left) and (C2) (on the right) in the definition of Ct(G, S). vertex-disjoint, the vertex v is outside H1, H2, H3, and for every i ∈ [3], the path Pi has its other endpoint in V (Hi) and is otherwise vertex-disjoint from H1, H2, H3; or (C2) H is the union of three vertex-disjoint subgraphs H1, H2, H3 ∈ Ct−1(G, S) and three paths P1, P2, P3 such that the interiors of P1, P2, P3 are pairwise … view at source ↗

**Figure 2.** Proof of Claim 10. The marked vertices, in red, are vertices in S, and the dashed paths, in green, are the paths P1, P2, P3 ∈ P. We find two vertex-disjoint subgraphs H1, H2 both containing a model of K1,3 in which leaf branch sets intersect S. Claim 10. For every H ∈ H and i ∈ {1, 2, 3}, at most two paths in P have an endpoint in the interior of QH,i. Proof of claim. Suppose there are H ∈ H, i ∈ {1, 2, 3} and P1, P… view at source ↗

**Figure 3.** Illustration for the proof of Theorem 11. The square shapes represent the elements of P and the potential connections between the considered objects are depicted in light gray. For every H ∈ Ct(G − (Z0 ∪ V ( S Z ′ 0 )), S), let IH = {i ∈ [ℓ] | V (H) ∩ V (Pi) ̸= ∅}. By the maximality of |P|, H intersects P \ Z ′ 0 , and so IH is nonempty. Moreover, because H is connected and by (⋆), we have that IH is an interval. B… view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Illustration of Claim 22 for ℓ = 10. Case (a) is depicted on the left and Case (b) on the right. The graph H ∈ H is in solid black, the vertices of S are red, and the paths in P are dashed green. In both cases, we find two vertex-disjoint S-rooted models of Pℓ , which …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 7 linked inside Pith

[9]

Quicklyexcludinganapex- forest.SIAM Journal on Discrete Mathematics, 40(1):282–307, 2026.arXiv:2404.17306

JędrzejHodor, HoangLa, PiotrMicek, andClémentRambaud. Quicklyexcludinganapex- forest.SIAM Journal on Discrete Mathematics, 40(1):282–307, 2026.arXiv:2404.17306

arXiv 2026
[1]

A tight Erdős-Pósa function for planar minors.Advances in Combinatorics, 2019.arXiv: 1807.04969

Wouter Cames van Batenburg, Tony Huynh, Gwenaël Joret, and Jean-Florent Raymond. A tight Erdős-Pósa function for planar minors.Advances in Combinatorics, 2019.arXiv: 1807.04969

arXiv 2019
[2]

Excluding an apex-forest or a fan as quickly as possible.arXiv preprint, 2026.arXiv:2602.03833

Quentin Claus, Jędrzej Hodor, Gwenaël Joret, and Pat Morin. Excluding an apex-forest or a fan as quickly as possible.arXiv preprint, 2026.arXiv:2602.03833

arXiv 2026
[3]

Blow-up structure of graphs excluding a tree or an apex-tree as a minor.arXiv preprint, 2026.arXiv:2603.16615

Quentin Claus, Gwenaël Joret, and Clément Rambaud. Blow-up structure of graphs excluding a tree or an apex-tree as a minor.arXiv preprint, 2026.arXiv:2603.16615

arXiv 2026
[4]

Graph minors I: A short proof of the path-width theorem.Combina- torics, Probability and Computing, 4:27–30, 1995

Reinhard Diestel. Graph minors I: A short proof of the path-width theorem.Combina- torics, Probability and Computing, 4:27–30, 1995

1995
[5]

Tight bound for the Erdős- Pósa property of tree minors.Combinatorics, Probability, and Computing, 34(2):321–325, 2025.arXiv:2403.06370

Vida Dujmović, Gwenaël Joret, Piotr Micek, and Pat Morin. Tight bound for the Erdős- Pósa property of tree minors.Combinatorics, Probability, and Computing, 34(2):321–325, 2025.arXiv:2403.06370

arXiv 2025
[6]

On independent circuits contained in a graph.Canadian Journal of Mathematics, 17:347–352, 1965

Paul Erdős and Lajos Pósa. On independent circuits contained in a graph.Canadian Journal of Mathematics, 17:347–352, 1965

1965
[7]

Samuel Fiorini, Gwenaël Joret, and David R. Wood. Excluded forest minors and the Erdős-Pósa property.Combinatorics, Probability and Computing, 22(5):700–721, 2013. arXiv:1204.5192

arXiv 2013

Show all 13 references

[8]

Approximating pathwidth for graphs of small treewidth.ACM Transactions on Algorithms, 19(2):1–19, 2023.arXiv:2008.00779

Carla Groenland, Gwenaël Joret, Wojciech Nadara, and Bartosz Walczak. Approximating pathwidth for graphs of small treewidth.ACM Transactions on Algorithms, 19(2):1–19, 2023.arXiv:2008.00779

2023 arXiv
[10]

Jansen and Céline M.F

Bart M.P. Jansen and Céline M.F. Swennenhuis. Steiner tree parameterized by multiway cut and even less. In32nd Annual European Symposium on Algorithms (ESA 2024), volume 308, pages 76:1–76:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi: 10.4230/LIPICS.ESA.202...

2024 arXiv
[11]

Colorfulminors

EvangelosProtopapas, DimitriosM.Thilikos, andSebastianWiederrecht. Colorfulminors. arXiv preprint, 2025.arXiv:2507.10467

2025 arXiv
[12]

Neil Robertson and Paul D. Seymour. Graph minors. I. Excluding a forest.Journal of Combinatorial Theory, Series B, 35(1):39–61, 1983

1983
[13]

Graphminors.V.Excludingaplanargraph.Journal of Combinatorial Theory, Series B, 41(1):92–114, 1986

NeilRobertsonandPaulD.Seymour. Graphminors.V.Excludingaplanargraph.Journal of Combinatorial Theory, Series B, 41(1):92–114, 1986

1986

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.

[1] [9]

Quicklyexcludinganapex- forest.SIAM Journal on Discrete Mathematics, 40(1):282–307, 2026.arXiv:2404.17306

JędrzejHodor, HoangLa, PiotrMicek, andClémentRambaud. Quicklyexcludinganapex- forest.SIAM Journal on Discrete Mathematics, 40(1):282–307, 2026.arXiv:2404.17306

arXiv 2026

[2] [1]

A tight Erdős-Pósa function for planar minors.Advances in Combinatorics, 2019.arXiv: 1807.04969

Wouter Cames van Batenburg, Tony Huynh, Gwenaël Joret, and Jean-Florent Raymond. A tight Erdős-Pósa function for planar minors.Advances in Combinatorics, 2019.arXiv: 1807.04969

arXiv 2019

[3] [2]

Excluding an apex-forest or a fan as quickly as possible.arXiv preprint, 2026.arXiv:2602.03833

Quentin Claus, Jędrzej Hodor, Gwenaël Joret, and Pat Morin. Excluding an apex-forest or a fan as quickly as possible.arXiv preprint, 2026.arXiv:2602.03833

arXiv 2026

[4] [3]

Blow-up structure of graphs excluding a tree or an apex-tree as a minor.arXiv preprint, 2026.arXiv:2603.16615

Quentin Claus, Gwenaël Joret, and Clément Rambaud. Blow-up structure of graphs excluding a tree or an apex-tree as a minor.arXiv preprint, 2026.arXiv:2603.16615

arXiv 2026

[5] [4]

Graph minors I: A short proof of the path-width theorem.Combina- torics, Probability and Computing, 4:27–30, 1995

Reinhard Diestel. Graph minors I: A short proof of the path-width theorem.Combina- torics, Probability and Computing, 4:27–30, 1995

1995

[6] [5]

Tight bound for the Erdős- Pósa property of tree minors.Combinatorics, Probability, and Computing, 34(2):321–325, 2025.arXiv:2403.06370

Vida Dujmović, Gwenaël Joret, Piotr Micek, and Pat Morin. Tight bound for the Erdős- Pósa property of tree minors.Combinatorics, Probability, and Computing, 34(2):321–325, 2025.arXiv:2403.06370

arXiv 2025

[7] [6]

On independent circuits contained in a graph.Canadian Journal of Mathematics, 17:347–352, 1965

Paul Erdős and Lajos Pósa. On independent circuits contained in a graph.Canadian Journal of Mathematics, 17:347–352, 1965

1965

[8] [7]

Samuel Fiorini, Gwenaël Joret, and David R. Wood. Excluded forest minors and the Erdős-Pósa property.Combinatorics, Probability and Computing, 22(5):700–721, 2013. arXiv:1204.5192

arXiv 2013