O-joung Kwon (권오정), Directed tangles and applications

The canonical tree-decomposition theorem, proved by Robertson and Seymour in their seminal graph minors series, turns out to be an extremely valuable tool in structural and algorithmic graph theory. In this paper, we prove the analogous result for digraphs, the directed tangle tree-decomposition theorem. More precisely, we introduce directed tangles and provide a directed tree-decomposition of digraphs $G$ that distinguishes all maximal directed tangles in $G$. Furthermore, for any integer $k$, we construct a directed tree-decomposition that distinguishes all directed tangles of order $k$, for any integer $k$.

By relaxing the bound slightly, we can make the previous result algorithmic: for fixed $k$, we design a polynomial-time algorithm that finds a directed tree-decomposition distinguishing all directed tangles of order $3k$ separated by some separation of order less than $k$.

We provide two direct applications of this tangle tree-decomposition theorem. First, we show that the family of directed odd cycles has the half-integral Erdős-Pósa property, that is, there is a function $f:\mathbb{N}\rightarrow \mathbb{R}$ such that for every digraph $G$ and every integer $k$, either $G$ contains a family of $k$ directed odd cycles where every vertex of $G$ is contained at most two cycles, or a vertex subset of size at most $f(k)$ hitting all directed odd cycles. This extends the half-integral Erdős-Pósa property for undirected odd cycles, shown by Reed [Mangoes and blueberries. Combinatorica 1999].

Second, for every fixed $k$ we show that there is a polynomial-time algorithm which, on input $G$, and source and sink vertices $(s_1, t_1), \dots, (s_k, t_k)$, either finds a family of paths $P_1, \dots, P_k$ such that each $P_i$ links $s_i$ to $t_i$ and every vertex of $G$ is contained in at most two paths, or determines that there is no set of pairwise vertex-disjoint paths each connecting $s_i$  to $t_i$. This result improves previous results (with “two” replaced by “three”), and given known hardness results, our result is best possible in a sense that we cannot hope for fixed parameter tractability or fully vertex-disjoint directed paths.

This is joint work with Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, and Qiqin Xie.