CS Paper Radar

A Polynomial Erdős-Pósa bound for Eulerian digraphs

Esther Galby, Roohani Sharma, Bart van der Steenhoven

cs.DM cs.DSmath.CO ·submitted 2026-11-04 09:58 UTC · v1
theory

Abstract

In [Combinatorica 1996], Reed, Robertson, Seymour and Thomas proved Younger's conjecture dating back to 1973 that states that directed cycles have the Erdős-Pósa property. Specifically, they showed that every directed graph $D$ contains either $k$ arc-disjoint cycles or a set of at most $f(k)$ arcs that intersect every directed cycle. The function $f$, depending only on $k$, is however notoriously large--in fact, not even elementary. The first improvement on this function was only very recently provided by Hatzel, Kreutzer, Milani, and Muzi [FOCS 2024] who showed that $f$ can be taken to be an exponential tower of height $8$. In this work, we improve this function to $O(k^4)$ in the case where the digraph is Eulerian. This also answers an open question by Wahlström [Springer Monographs in Mathematics 2018] who asked explicitly when Eulerian digraphs have a polynomial Erdős-Pósa property. The only other known result about Erdős-Pósa on Eulerian digraphs is a result from Seymour [Combinatorica 1996] who showed that $f(k)=k$ when the Eulerian digraph admits a linkless embedding in 3-space, and such an equality is not possible for general Eulerian digraphs. We also complement our positive result, by showing that the result of Seymour cannot be extended to give a linear bound ($O(k)$) on general Eulerian digraphs, by showing that even on Eulerian digraphs the lower bound for the Erdős-Pósa property is $Ω(k \log k)$.

Closest papers

Nearest neighbours by meaning across the whole index.

A relaxation of the Bermond-Thomassen conjecture

cs.DM math.CO ·2026-08-13 ·Stéphane Bessy, Matthijs Muis, Jean-Sébastien Sereni, Raphael Steiner, Sebastian Wiederrecht
theory similarity 0.70
Abstract · 10 pages, 1 figure

The well-known Bermond-Thomassen conjecture states that every digraph of minimum out-degree at least $2k-1$ contains $k$ vertex-disjoint directed cycles. Despite being posed in 1981, this conjecture remains unresolved for all $k \ge 4$. We prove a relaxation of this conjecture: every digraph $D$ of minimum out-degree at least $2k-1$ contains $k$ vertex-disjoint cycles, each of which either is directed or can be made directed by reversing one of its arcs. This bound is sharp and answers a question raised by Cames van Batenburg during the online workshop "Entropy Compression and Related Methods" in $2021$.

0.38

A linear bound for nested cycles without geometric crossings

cs.DM math.CO ·2026-09-02 ·Jiangdong Ai, Gregory Gutin, Yiming Hao
theoryhot direction similarity 0.68
Abstract

Cycles $C_1,\ldots,C_k$ in a graph are called nested without geometric crossings if they are pairwise edge-disjoint, $V(C_k)\subseteq\cdots\subseteq V(C_1)$, and each pair of consecutive cycles induces the same cyclic order on the vertices of the inner cycle, up to reversal. Let $f_k(n)$ be the least number of edges that forces such a family in every $n$-vertex graph. Gil Fernández, Kim, Kim and Liu proved that $f_2(n)=O(n)$, answering a question of Erdős, and asked whether $f_k(n)=O_k(n)$ for every fixed $k$. We prove this for all $k$. The proof selects the inner cycles together with a disjoint subgraph that supplies their external neighbours. A reselection argument gives disjoint paths from every inner-cycle vertex to any sufficiently large target set. Sublinear expansion and a rooted clique minor then allow the vertices to be joined in the required cyclic order.

0.25

Erdős-Pósa property for induced packings of long $S$-cycles

cs.DM math.CO ·2026-08-23 ·Jungho Ahn, O-joung Kwon
theory similarity 0.67
Abstract · 50 pages and 2 figures

The Erdős-Pósa theorem states that for every integer $k\geq1$, every graph contains either $k$ vertex-disjoint cycles or a set of $\mathcal{O}(k\log k)$ vertices meeting all cycles. This fundamental min-max duality has been extended to numerous settings, including long cycles, $S$-cycles, that is, cycles containing a vertex in a prescribed set $S$, and cycles satisfying various additional constraints. In contrast, much less is known when the packing itself is required to be induced, namely, when distinct cycles are vertex-disjoint and have no edges between them. We prove that long $S$-cycles admit an induced version of the Erdős-Pósa-type duality. More precisely, we show that there exists a polynomial function $f(k,\ell)$ such that for all integers $k\geq1$ and $\ell\geq3$, every graph contains either an induced packing of $k$ $S$-cycles of length at least $\ell$ or a set of at most $f(k,\ell)$ vertices whose closed neighbourhood intersects all $S$-cycles of length at least $\ell$. The proof introduces a new ear-decomposition technique based on fragile ears and yields a polynomial-time algorithm for every fixed $\ell$.

0.14

Single-Exponential Algorithms for Directed Feedback Vertex Set on Planar Digraphs

cs.DS ·2026-09-26 ·Daniel Lokshtanov, Saket Saurabh, Jie Xue
theory similarity 0.66
Abstract

We consider Directed Feedback Vertex Set on planar digraphs, parameterized by the solution size $k$. We give a randomized algorithm with one-sided error running in time $(2+\sqrt5)^k n^{O(1)}= 4.24^k n^{O(1)}$, and a deterministic algorithm running in time $8.04^k n^{O(1)}$. Both algorithms use polynomial space. To the best of our knowledge, these are the first single-exponential fixed-parameter algorithms for Directed Feedback Vertex Set on planar digraphs. This contrasts with general digraphs, where the best known algorithms run in time $2^{O(k\log k)}(n+m)$, and whether a $2^{o(k\log k)}n^{O(1)}$-time algorithm exists remains a major open problem. Our main tool is an exact Euler-type counting identity for plane digraphs. It shows that every small solution must carry a large share of the vertices whose in- and out-arcs alternate in the embedding, while solutions avoiding such vertices can be computed by reducing to Directed Feedback Arc Set, which is known to be solvable in polynomial time on planar digraphs via the Lucchesi-Younger theorem.

0.38

An Improved Bound for Smith's Longest Cycles Conjecture via a Forbidden Subdivision

cs.DM math.CO ·2026-08-31 ·Douglas M. Chen
hot direction similarity 0.65
Abstract · 9 pages, 2 figures. Comments welcome!

Smith's conjecture asserts that in every $k$-connected graph with $k\geq 2$, any two longest cycles intersect in at least $k$ vertices. In this work, we establish an $Ω(k^{8/11})$ bound for this conjecture, improving upon the $Ω(k^{2/3})$ bound of Ma and Zhao. Our proof combines a Ramsey theoretic refinement of the traditional Turán-type approach with computer search.

0.50

Polynomial bounds for quasiplanar graphs

cs.CG math.CO ·2026-11-16 ·Aleksa Milojević, Patryk Morawski, Benny Sudakov, Istvan Tomon
theory similarity 0.64
Abstract · 11 pages

A graph $G$ is $k$-quasiplanar if it can be drawn in the plane without $k$ pairwise crossing edges. It was a longstanding conjecture that $n$-vertex $k$-quasiplanar graphs have $O_k(n)$ edges. This was recently resolved by Sadhu and, independently, by Pach, Tardos, and Zeng, based on a theorem in topology proven by Beeker and Lazarovich. These papers showed that $k$-quasiplanar graphs have at most $k^{O(k)}n$ edges. In this note, we greatly improve the dependence on $k$ and show that every $k$-quasiplanar $n$-vertex graph has at most $O(k^2n)$ edges. The proof is based on a geometric charging scheme and Erdős-Szekeres type combinatorial arguments.

0.21

An Erdős-Pósa theorem for induced packings of even cycles

cs.DM math.CO ·2026-10-16 ·Jungho Ahn, Lars Jaffke, O-joung Kwon, Paloma T. de Lima, Hyemi Park
theory similarity 0.63
Abstract · 38 pages, 5 figures

We show that for every graph $G$ and every positive integer $k$, $G$ contains either $k$ vertex-disjoint even cycles with no edges between distinct cycles, or a set of $O(k^2\log k)$ vertices whose closed neighborhood meets every even cycle of $G$. Moreover, we give a polynomial-time algorithm that outputs one of the two outcomes. As an application, we show that every $K_{1,t}$-free graph containing no induced packing of $k$ even cycles has tree-independence number $O(tk^2\log k)$, with a corresponding decomposition computable in polynomial time.

0.10

Sharp bounds and extremal structure of minimally strongly $k$-connected digraphs

cs.DM math.CO ·2026-10-10 ·Junran Yu, Gregory Gutin, Hong-Jian Lai, Xiaoyan Zhang
theory similarity 0.63
Abstract

Let $D$ be a finite simple minimally strongly $k$-connected digraph, where $k\ge 2$, and let $n=|V(D)|$. Mader proved in 1985 that $|A(D)|\le 2k(n-k)$ for all sufficiently large $n$, with equality if and only if $D\cong \overleftrightarrow{K}_{k,n-k}$ (JCTB 1985). We prove that this bound holds whenever $n\ge 3k-1$ and that the order threshold $3k-1$ is best possible. Moreover, if $n\ge 3k$, then equality holds if and only if $D\cong \overleftrightarrow{K}_{k,n-k}$. The threshold $3k$ is also best possible. These results resolve the conjecture of Mader in (JCTB 1985).

0.21