DAG-width and circumference of digraphs

Jørgen Bang-Jensen, Tilde My Larsen

We prove that every digraph of circumference $l$ has DAG-width at most $l$ and this is best possible. As a consequence of our result we deduce that the $k$-linkage problem is polyn…