Packing directed circuits (Q1375699)

The authors prove Younger's conjecture, which states that for every integer \(n \geq 0\) there exists an integer \(t \geq 0\) such that any digraph \(G\) has either \(n\) vertex-disjoint directed circuits, or \(G\) can be made acyclic by deleting at most \(t\) vertices. The bound for \(t\) is a multiply iterated exponential in terms of \(n\), where the number of iterations is also multiply exponential. A polynomial algorithm testing if \(\nu (G) \geq n\) for a digraph \(G\) is also given.