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$f$such that every digraph of directed tree-width$f(k)$contains a cylindrical grid of order$k$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$f$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]).

Given two disjoint sets W1 and W2 of points in the plane, the Optimal Discretization problem asks for the minimum size of a family of horizontal and vertical lines that separate W1 from W2, that is, in every region into which the lines partition the plane there are either only points of W1, or only points of W2, or the region is empty. Equivalently, Optimal Discretization can be phrased as a task of discretizing continuous variables: We would like to discretize the range of x-coordinates and the range of y-coordinates into as few segments as possible, maintaining that no pair of points from W1 × W2 are projected onto the same pair of segments under this discretization. We provide a fixed-parameter algorithm for the problem, parameterized by the number of lines in the solution. Our algorithm works in time , where k is the bound on the number of lines to find and n is the number of points in the input. Our result answers in positive a question of Bonnet, Giannopolous, and Lampis [IPEC 2017] and of Froese (PhD thesis, 2018) and is in contrast with the known intractability of two closely related generalizations: the Rectangle Stabbing problem and the generalization in which the selected lines are not required to be axis-parallel.

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 O(k log k). After being known for long as Younger’s conjecture, a similar statement for directed graphs has been proven in 1996 by Reed, Robertson, Seymour, and Thomas. However, in their proof, the dependency of the size of the feedback vertex set on the size of vertex-disjoint cycle packing is not elementary. We show that if we compare the size of a minimum feedback vertex set in a directed graph with quarter-integral cycle packing number, we obtain a polynomial bound. More precisely, we show that if in a directed graph G there is no family of k cycles such that every vertex of G is in at most four of the cycles, then there exists a feedback vertex set in G of size O(k^4). On the way there we prove a more general result about quarter-integral packing of subgraphs of high directed treewidth: for every pair of positive integers a and b, if a directed graph G has directed treewidth Omega(a^6 b^8 log^2(ab)), then one can find in G a family of a subgraphs, each of directed treewidth at least b, such that every vertex of G is in at most four subgraphs.

The notions of bounded expansion [Nešetřil and Ossona de Mendez, 2008] and nowhere denseness [Nešetřil and Ossona de Mendez, 2011], introduced by Nešetřil and Ossona de Mendez as structural measures for undirected graphs, have been applied very successfully in algorithmic graph theory. We study the corresponding notions of directed bounded expansion and nowhere crownfulness on directed graphs, introduced by Kreutzer and Tazari [Kreutzer and Tazari, 2012]. The classes of directed graphs having those properties are very general classes of sparse directed graphs, as they include, on one hand, all classes of directed graphs whose underlying undirected class has bounded expansion, such as planar, bounded-genus, and H-minor-free graphs, and on the other hand, they also contain classes whose underlying undirected class is not even nowhere dense. We show that many of the algorithmic tools that were developed for undirected bounded expansion classes can, with some care, also be applied in their directed counterparts, and thereby we highlight a rich algorithmic structure theory of directed bounded expansion and nowhere crownful classes.

We study the half-integral $k$-Directed Disjoint Paths Problem ($\tfrac12$kDDPP) in highly strongly connected digraphs. The integral kDDPP is NP-complete even when restricted to instances where $k=2$, and the input graph is $L$-strongly connected, for any $L\geq 1$. We show that when the integrality condition is relaxed to allow each vertex to be used in two paths, the problem becomes efficiently solvable in highly connected digraphs (even with $k$ as part of the input). Specifically, we show that there is an absolute constant $c$ such that for each $k\geq 2$ there exists $L(k)$ such that $\tfrac12$kDDPP is solvable in time $O(|V(G)|^c)$ for a $L(k)$-strongly connected directed graph $G$. As the function $L(k)$ grows rather quickly, we also show that $\tfrac12$kDDPP is solvable in time $O(|V(G)|^{f(k)})$ in $(36k^3+2k)$-strongly connected directed graphs. We also show that for each $ε<1$ deciding half-integral feasibility of kDDPP instances is NP-complete when $k$ is given as part of the input, even when restricted to graphs with strong connectivity $εk$.

We study the computational complexity of identifying dense substructures, namely r/2-shallow topological minors and r-subdivisions. Of particular interest is the case r = 1, when these substructures correspond to very localized relaxations of subgraphs. Since Densest Subgraph can be solved in polynomial time, we ask whether these slight relaxations also admit efficient algorithms. In the following, we provide a negative answer: Dense r/2-Shallow Topological Minor and Dense r-Subdivsion are already NP-hard for r = 1 in very sparse graphs. Further, they do not admit algorithms with running time 2^(o(tw^2)) n^O(1) when parameterized by the treewidth of the input graph for r > 2 unless ETH fails.

Let ${\cal G}$ be a family of $n$-vertex graphs of uniform degree 2 with the property that the union of any two member graphs has maximum degree 4. We determine the leading term in the asymptotics of the largest cardinality of such a family. Several analogous problems are discussed.