Long Cycles Get Sharp Far-Apart Erdős–Pósa Bounds

Classical Erdős–Pósa theory asks whether a graph either contains many disjoint copies of a structure or has a small vertex set hitting all of them. This paper studies a stricter metric version for long cycles: the packed cycles must be far apart, and the covering set is allowed to remove a bounded-radius neighborhood rather than just individual vertices. The authors prove that long cycles satisfy this far-apart version with asymptotically tight dependence on the number of cycles and a best-possible linear dependence on distance.

Core Contribution

The main theorem says that for all positive integers $k$, $d$, and $\ell \geq 3$, every graph $G$ has one of two outcomes. Either $G$ contains $k$ cycles of length at least $\ell$ that are pairwise at distance greater than $d$, or there is a vertex set $X$ of controlled size such that deleting a ball of radius $g(d)$ around $X$ leaves no cycle of length at least $\ell$.

Quantitatively, the paper proves $f(k,\ell) \in O(\ell k\log k)$ and $g(d) \in O(d)$. This extends the earlier far-apart theorem for ordinary cycles, the case $\ell=3$, to long cycles. It also improves the known bound for that case from $O(k^{18}\operatorname{polylog} k)$ to the optimal $O(k\log k)$ order in $k$.

The result is purely structural. Its value is not in an algorithm or experiment, but in showing that the metric strengthening of Erdős–Pósa survives the additional length constraint without paying more than a linear factor in $\ell$.

Technical Approach

The proof works by replacing direct cycle hitting with a controlled decomposition around a maximal collection of long cycles. A central device is a notion of span measured through BFS-spanning subgraphs supported on an existing family of cycles. Edges whose span is too large are treated as sources of new long cycles; otherwise, bounded-span structure lets the authors push any remaining long cycle close to a small set of cycle vertices.

Theorem 18 then assembles these local controls into the advertised global bound. The displayed functions are

Here $s(k)$ is the earlier packing-covering bound used by the argument, giving the final $O(\ell k\log k)$ estimate. The proof starts from maximal families of long cycles: one family $\mathcal{Z}$ of cycles with lengths between $\ell$ and $6d+2$, and another family $\mathcal{C}$ with controlled span inside $d$-balls. Claim 19 shows that every long cycle must meet $B_G(\bigcup\mathcal{C},4d)\cup B_G(\bigcup\mathcal{Z},4d)$; otherwise Lemma 7 would produce an additional cycle contradicting maximality. Claims 20 and the following estimates then convert this proximity statement into an explicit hitting set.

Results and Analysis

The strongest quantitative statement is Theorem 18: either a graph contains a $d$-packing of $k$ cycles of length at least $\ell$, or deleting $B_G(X,21d)$ for a set $X$ of size at most $f(k,\ell)$ kills all cycles of length at least $\ell$. The constant $21$ is not presented as the best constant, but the linear dependence on $d$ is claimed to be optimal in order.

For the size of $X$, the bound $O(\ell k\log k)$ matches the best possible dependence on $k$ for every fixed $\ell$. That is the main improvement over prior far-apart work: when $\ell=3$, the previous bound was $O(k^{18}\operatorname{polylog} k)$, so the new theorem moves the dependence in $k$ from a large polynomial to the known optimal order.

The evidence is a formal proof, not empirical validation. The proof is detailed and quantitative, with explicit constants in the final theorem and intermediate claims controlling where long cycles can remain after bounded-radius deletions. The trade-off is that the result is existential and structural: it does not by itself give a practical graph algorithm, and the constants in the displayed bound are large enough that the theorem is more informative asymptotically than computationally.