Packing Directed Cycles Quarter- and Half-Integrally

Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Pawel Rzazewski, Manuel SorgeComb 2022 · OpenReview

TL;DR

This paper bridges a gap in understanding the relationship between cycle structures and "bottlenecks" (feedback vertex sets) in directed graphs. By introducing the concepts of "quarter-integral" and "half-integral" cycle packings, the authors prove that these relaxed notions of cycle packing lead to polynomial bounds on the size of feedback vertex sets, a significant improvement over previous nonelementary results.

What Problem Does This Paper Address?

The Erdős-Pósa theorem for undirected graphs establishes a fundamental connection: if a graph doesn't contain many vertex-disjoint cycles, it must have a relatively small set of vertices (a feedback vertex set) that hits all cycles. While a similar theorem exists for directed graphs, its proof is complex and doesn't yield a simple, polynomial relationship between the number of disjoint cycles and the size of the feedback vertex set. This paper tackles this issue by exploring what happens when we relax the "vertex-disjoint" condition. Instead of requiring cycles to be completely separate, they consider scenarios where vertices can be part of a few cycles. Specifically, they investigate "quarter-integral" packings (each vertex in at most 4 cycles) and "half-integral" packings (each vertex in at most 2 cycles). The core question is whether these relaxed packing conditions can lead to more manageable, polynomial bounds on the feedback vertex set size.

Methods

The authors leverage the concept of "directed treewidth," a measure of how "tree-like" a directed graph is, and its connection to "linkages" (sets of vertex-disjoint paths). A key technique is the use of "partitioning lemmas" to break down complex graph structures into smaller, more manageable pieces. They also employ "backlinkage-induced orders" and auxiliary graphs to analyze the relationships between different sets of paths and cycles. The proofs often involve inductive arguments and careful counting of edges and vertices to establish lower bounds on directed treewidth and upper bounds on feedback vertex set sizes. A significant contribution is the development of a new "partitioning tool" to handle dense intersection scenarios, which is crucial for achieving their results.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Relaxing Disjointness is Key: The most significant insight is that by allowing vertices to be shared among cycles (up to a constant limit), we can achieve polynomial bounds on feedback vertex sets, which was not possible with strictly vertex-disjoint cycles.
  • Quarter-Integral is Better: The paper shows that a quarter-integral packing (vertices in at most 4 cycles) leads to a better bound (O(k⁴)) than a half-integral packing (vertices in at most 2 cycles, leading to O(k⁶)). This suggests a trade-off between packing density and the resulting feedback vertex set size.
  • Directed Treewidth as a Bridge: Directed treewidth proves to be a powerful tool, acting as an intermediary to connect cycle packing properties with feedback vertex set sizes.
  • New Partitioning Technique: The authors introduce a novel partitioning lemma that is essential for handling "dense" intersection scenarios in their proofs, particularly for proving Theorem 5.

Key Results

The paper establishes the following bounds for a directed graph $G$ that does not contain a family of $k$ cycles such that every vertex in $G$ is contained in at most $p$ cycles:

  • If $p=4$ (quarter-integral packing), there exists a feedback vertex set of size $O(k^4)$.
  • If $p=3$, there exists a feedback vertex set of size $O(k^5)$.
  • If $p=2$ (half-integral packing), there exists a feedback vertex set of size $O(k^6)$.

Furthermore, they prove a related result about packing subgraphs of high directed treewidth, showing that a graph with high directed treewidth contains a quarter-integral packing of subgraphs with high directed treewidth.

Limitations and Future Work

The authors acknowledge that their results for packing subgraphs of high directed treewidth (Theorem 5) are "quarter-integral" rather than "integral" (vertex-disjoint), which is a limitation compared to analogous results in undirected graphs. They also note that the proof of Theorem 5 relies on Lemma 7, which has a quadratic blow-up, and they suggest that avoiding this might lead to better bounds. A key open question is whether the dependency on $k$ can be further reduced, or if a constant $c$ and a polynomial $p(log k)$ can bound the directed treewidth by $O(k \cdot p(\log k))$ for a constant congestion $c$. They also pose a question about whether a constant congestion $c$ and a polynomial $p$ can bound the directed treewidth by $O(k \cdot p(\log k))$ for a constant congestion $c$.

Summary updated

Abstract

The celebrated Erdős-Pósa theorem states that every undirected graph that does not admit a family of k vertex-disjoint cycles contains a feedback vertex set (a set of vertices hitting all cycles in the graph) of size \(\cal{O}(k\log k)\). The analogous result for directed graphs has been proven by Reed, Robertson, Seymour, and Thomas, but their proof yields a nonelementary dependency of the size of the feedback vertex set on the size of vertex-disjoint cycle packing.
BibTeX
@inproceedings{masarik2022packing,
  author = {Tomás Masarík and Irene Muzi and Marcin Pilipczuk and Pawel Rzazewski and Manuel Sorge},
  title = {{Packing Directed Cycles Quarter- and Half-Integrally}},
  booktitle = {Comb},
  year = {2022},
  url = {https://openreview.net/forum?id=AMSbHw8Wbi},
}
Figure