Jungles, bundles, and fixed parameter tractability

Fedor V. Fomin, Michał Pilipczuk

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.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment