Cycles of Well-Linked Sets I: an Elementary Bound for Directed Cycle Packing
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908836875468800 |
|---|---|
| author | Hatzel, Meike Kreutzer, Stephan Milani, Marcelo Garlet Muzi, Irene |
| author_facet | Hatzel, Meike Kreutzer, Stephan Milani, Marcelo Garlet Muzi, Irene |
| contents | In 1996, Reed, Robertson, Seymour and Thomas [Combinatorica 1996] proved Younger's Conjecture, which states that, for all directed graphs $D$, there exists a function $f$ such that, if $D$ does not contain $k$ disjoint cycles, then $D$ contains a feedback vertex set, i.e.~a subset of vertices whose deletion renders the graph acyclic, of size bounded by $f(k)$. However, the function obtained by Reed, Robertson, Seymour and Thomas in their paper is enormous and, in fact, not even elementary. We prove the first elementary upper bound for the function $f$ above, showing it is upper-bounded by a power tower of height 8.
Our proof is inspired by the breakthrough result of Chekuri and Chuzhoy [J. ACM 2016], who proved a polynomial bound for the Excluded Grid Theorem for undirected graphs. We translate a key concept of their proof to directed graphs by introducing paths of well-linked sets (PWS), and show that any digraph of large directed treewidth contains a large PWS, which in turn contains a large fence.
We believe that the theoretical tools developed in this work may find applications beyond the results above, in a similar way as the path-of-sets-system framework due to Chekuri and Chuzhoy [J. ACM 2016] did for undirected graphs (see, for example, Hatzel, Komosa, Pilipczuk and Sorge [Discret. Math. Theor. Comput. Sci. 2022], Chekuri and Chuzhoy [SODA 2015] and Chuzhoy and Nimavat [arXiv 2019]). Indeed, in a follow-up paper, we apply this framework to improve the bounds of the Directed Grid Theorem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_19222 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Cycles of Well-Linked Sets I: an Elementary Bound for Directed Cycle Packing Hatzel, Meike Kreutzer, Stephan Milani, Marcelo Garlet Muzi, Irene Discrete Mathematics Combinatorics 05C20, 05C83, 68R10 In 1996, Reed, Robertson, Seymour and Thomas [Combinatorica 1996] proved Younger's Conjecture, which states that, for all directed graphs $D$, there exists a function $f$ such that, if $D$ does not contain $k$ disjoint cycles, then $D$ contains a feedback vertex set, i.e.~a subset of vertices whose deletion renders the graph acyclic, of size bounded by $f(k)$. However, the function obtained by Reed, Robertson, Seymour and Thomas in their paper is enormous and, in fact, not even elementary. We prove the first elementary upper bound for the function $f$ above, showing it is upper-bounded by a power tower of height 8. Our proof is inspired by the breakthrough result of Chekuri and Chuzhoy [J. ACM 2016], who proved a polynomial bound for the Excluded Grid Theorem for undirected graphs. We translate a key concept of their proof to directed graphs by introducing paths of well-linked sets (PWS), and show that any digraph of large directed treewidth contains a large PWS, which in turn contains a large fence. We believe that the theoretical tools developed in this work may find applications beyond the results above, in a similar way as the path-of-sets-system framework due to Chekuri and Chuzhoy [J. ACM 2016] did for undirected graphs (see, for example, Hatzel, Komosa, Pilipczuk and Sorge [Discret. Math. Theor. Comput. Sci. 2022], Chekuri and Chuzhoy [SODA 2015] and Chuzhoy and Nimavat [arXiv 2019]). Indeed, in a follow-up paper, we apply this framework to improve the bounds of the Directed Grid Theorem. |
| title | Cycles of Well-Linked Sets I: an Elementary Bound for Directed Cycle Packing |
| topic | Discrete Mathematics Combinatorics 05C20, 05C83, 68R10 |
| url | https://arxiv.org/abs/2404.19222 |