Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem

In 2015, Kawarabayashi and Kreutzer proved the directed grid theorem - the generalisation of the well-known excluded grid theorem to directed graphs - confirming a conjecture by Reed, Johnson, Robertson, Seymour, and Thomas from the mid-nineties. The theorem states the existence of a function <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f$</tex> such that every digraph of directed tree-width <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f(k)$</tex> contains a cylindrical grid of order <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex> as a butterfly minor, but the given function grows non-elementarily with the size of the grid minor. More precisely, it contains a tower whose height depends on the size of the grid. In this paper, we present an alternative proof of the directed grid theorem which is conceptually much simpler, more modular in its composition and also improves the upper bound for the function <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f$</tex> to a power tower of height 22. Our proof is inspired by the breakthrough result of Chekuri and Chuzhoy, 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 cycles of well-linked sets (CWS), and show that any digraph of high directed tree-width contains a large CWS, which in turn contains a large cylindrical grid, improving the result due to Kawarabayashi and Kreutzer from a non-elementary to an elementary function. An immediate application of our result is that we can improve the bound for Younger's conjecture-the directed Erdős-Pósa property-proved by Reed, Robertson, Seymour and Thomas [2] from a non-elementary to an elementary function. The same improvement applies to other types of Erdős-Pósa style problems on directed graphs. To the best of our knowledge, this is the first significant improvement on the bound for Younger's conjecture since it was proved in 1996. Since its publication in STOC 2015, the Directed Grid Theorem has found numerous applications (see for example [3]–[7]), all of which directly benefit from our main result. Finally, we believe that the theoretical tools developed in this work may find applications beyond the directed grid theorem, in a similar way as the path-of-sets-system framework due to Chekuri and Chuzhoy [8] did for undirected graphs (see for example [9]–[11]).