ErdH{o}s--P\'{o}sa property of cycles that are far apart
Pith reviewed 2026-05-23 06:51 UTC · model grok-4.3
The pith
Any graph has either k cycles with all pairwise distances exceeding d or a set X of size at most f(k) whose g(d)-neighborhood deletion leaves a forest.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
There exist functions f,g:ℕ→ℕ such that for all nonnegative integers k and d, for every graph G, either G contains k cycles such that vertices of different cycles have distance greater than d in G, or there exists a subset X of vertices of G with |X|≤f(k) such that G−B_G(X,g(d)) is a forest.
What carries the argument
Distance-d separated cycle packing versus bounded-radius ball hitting set that reduces the graph to a forest.
If this is right
- When d is fixed the property yields a finite function f(k) that trades separated cycle packing against a local deletion to acyclicity.
- The classical Erdős-Pósa property for vertex-disjoint cycles is recovered in the limit as d approaches zero.
- The result supplies a uniform way to reduce any graph to a forest after paying a cost that depends only on the desired number of separated cycles and the separation distance.
- Any algorithm that solves feedback vertex set on forests immediately extends to the separated-cycle setting via the small set X and its bounded neighborhood.
Where Pith is reading between the lines
- The same functions f and g may be useful for designing approximation algorithms that find many well-separated cycles or certify that few exist.
- The property could be tested on minor-closed graph classes where the radius-g(d) deletion interacts cleanly with excluded minors.
- One could ask whether the same statement holds when the target after deletion is a graph of bounded treewidth rather than a forest.
Load-bearing premise
The structure of arbitrary graphs permits the number of mutually distant cycles to be bounded by a function of a small vertex set together with a fixed-radius neighborhood around it.
What would settle it
A single graph G together with integers k and d for which no set X of size at most f(k) exists making G minus the g(d)-ball around X a forest, yet G also lacks k cycles with pairwise distances greater than d.
read the original abstract
We prove that there exist functions $f,g:\mathbb{N}\to\mathbb{N}$ such that for all nonnegative integers $k$ and $d$, for every graph $G$, either $G$ contains $k$ cycles such that vertices of different cycles have distance greater than $d$ in $G$, or there exists a subset $X$ of vertices of $G$ with $|X|\leq f(k)$ such that $G-B_G(X,g(d))$ is a forest, where $B_G(X,r)$ denotes the set of vertices of $G$ having distance at most $r$ from a vertex of $X$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves that there exist functions f,g:ℕ→ℕ such that for all nonnegative integers k and d, for every graph G, either G contains k cycles with pairwise distances >d or there is a set X with |X|≤f(k) such that G−B_G(X,g(d)) is a forest.
Significance. This establishes a distance-sensitive variant of the Erdős–Pósa property for cycles. If correct, the result strengthens the classical cycle EP theorem by controlling the packing of mutually distant cycles via a bounded-radius hitting set that leaves only a forest. The manuscript contains no machine-checked proofs or explicit parameter bounds, but the existential claim is a direct structural statement in the spirit of known minor-closed and packing results.
major comments (1)
- [Abstract and §3] Abstract (and presumably the main theorem statement): the claim is quantified over every graph G with no finiteness restriction. The argument in §3 proceeds by induction on |V(G)| and reduction to the classical cycle EP property via distance-g(d) clusters; this induction does not apply to infinite graphs. In an infinite graph containing infinitely many mutually d-far cycles, no finite f(k) can hit all of them, so either the statement must be restricted to finite graphs or a separate compactness/compactness-free argument must be supplied.
minor comments (2)
- [§2] Notation: B_G(X,r) is used without an explicit reminder that it is the closed ball; a one-sentence definition in §2 would improve readability.
- [§4] The functions f and g are shown to exist but no explicit bounds or growth rates are derived; if the paper intends only existence this is acceptable, but a remark on computability would be useful.
Simulated Author's Rebuttal
Thank you for the detailed review. We address the major comment regarding the applicability to infinite graphs below.
read point-by-point responses
-
Referee: [Abstract and §3] Abstract (and presumably the main theorem statement): the claim is quantified over every graph G with no finiteness restriction. The argument in §3 proceeds by induction on |V(G)| and reduction to the classical cycle EP property via distance-g(d) clusters; this induction does not apply to infinite graphs. In an infinite graph containing infinitely many mutually d-far cycles, no finite f(k) can hit all of them, so either the statement must be restricted to finite graphs or a separate compactness/compactness-free argument must be supplied.
Authors: We agree with the observation that the inductive proof in §3 is valid only for finite graphs. Note that in an infinite graph with infinitely many mutually d-far cycles, the packing condition is satisfied for any k, so the statement holds without needing a bounded hitting set. However, to ensure the proof covers the claim, we will restrict the theorem to finite graphs G. This is a minor clarification, as Erdős–Pósa-type results are typically stated for finite graphs. We will revise the abstract and the main theorem statement to specify 'finite graph G'. revision: yes
Circularity Check
No circularity; existential claim on f and g is a standard structural theorem statement
full rationale
The manuscript asserts the existence of functions f and g satisfying a quantified statement over all graphs G, k, and d. No equations, parameters, or derivations appear in the abstract or theorem statement. The claim does not define any quantity in terms of itself, rename a known result, or rely on a load-bearing self-citation whose content reduces to the present result. Without visible proof steps that reduce by construction to fitted inputs or prior self-citations, the derivation chain (if present) cannot be shown to collapse. This matches the default expectation for non-circular papers in structural graph theory.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard axioms of graph theory: undirected graphs, simple paths, distance defined by shortest-path length.
Reference graph
Works this paper leans on
-
[1]
Pascal Gollin, Tony Huynh, and O-joung Kwo n
Jungho Ahn, J. Pascal Gollin, Tony Huynh, and O-joung Kwo n. A coarse Erd ős-Pósa theorem. In ACM-SIAM Symposium on Discrete Algorithms (SODA25). 2025. To appear
work page 2025
-
[2]
On independent circuits contained in a graph
Paul Erd ős and Lajos Pósa. On independent circuits contained in a graph. Canadian Journal of Mathematics, 17:347–352, 1965
work page 1965
-
[3]
Agelos Georgakopoulos and Panos Papasoglu. Graph minor s and metric spaces, 2023. arXiv:2305.07456
-
[4]
András Gyárfás and Jenö Lehel. A Helly-type problem in trees . Combinatorial Theory and its applications, 4:571–584, 1970
work page 1970
-
[5]
Neil Robertson and Paul D. Seymour. Graph minors. V. Excludi ng a planar graph. Journal of Combinatorial Theory, Series B , 41(1):92–114, 1986
work page 1986
-
[6]
Miklós Simonovits. A new proof and generalizations of a theo rem of Erd ős and Pósa on graphs without k + 1 independent circuits. Acta Mathematica Academiae Scientiarum Hungarica, 18:191–206, 1967. Appendix In this appendix, we present a complete proof of Theorem 3 and show that, for any fixed c, the bounding function ℓ⋆ (k, c ) is polynomial in k. All of ...
work page 1967
-
[7]
By the inductive hypothesis, there exists B′ 1,
implies that IB := (1, m, k −1, (Fi )i∈[c], (Bj )j∈[m], (yj )j∈[m]) is an (1, m, k −1)-instance. By the inductive hypothesis, there exists B′ 1, . . . , B′ m that satisfy IB . For each j ∈[m]\{ℓ}, let A′ j := B′ j and let A′ ℓ := {ˇA}∪B′ ℓ. Then the sequence A′ 1, . . . , A′ m satisfies I . This completes the proof of the case c = 1. Now suppose that c > 1...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.