Directed Minors III. Directed Linked Decompositions

Thomas proved that every undirected graph admits a linked tree decomposition of width equal to its treewidth.

In this paper, we generalize Thomas's theorem to digraphs.

We prove that every digraph G admits a linked directed path decomposition and a linked DAG decomposition of width equal to its directed pathwidth and DAG-width respectively.