Jungles, bundles, and fixed parameter tractability

Abstract

We give a fixed-parameter tractable (FPT) approximation algorithm computing the path-width of a tournament, and more generally, of a semi-complete digraph. Based on this result, we prove that topological containment and rooted immersion problems are FPT on semi-complete digraphs.

arXiv commentThe new version contains simplified proofs providing better running times of the algorithms, as well as a wider discussion of the context