  The notions of cutwidth and pathwidth of digraphs play a central role in the
containment theory for tournaments, or more generally semi-complete digraphs,
developed in a recent series of papers by Chudnovsky, Fradkin, Kim, Scott, and
Seymour [2, 3, 4, 8, 9, 11]. In this work we introduce a new approach to
computing these width measures on semi-complete digraphs, via degree orderings.
Using the new technique we are able to reprove the main results of [2, 9] in a
unified and significantly simplified way, as well as obtain new results. First,
we present polynomial-time approximation algorithms for both cutwidth and
pathwidth, faster and simpler than the previously known ones; the most
significant improvement is in case of pathwidth, where instead of previously
known O(OPT)-approximation in fixed-parameter tractable time [6] we obtain a
constant-factor approximation in polynomial time. Secondly, by exploiting the
new set of obstacles for cutwidth and pathwidth, we show that topological
containment and immersion in semi-complete digraphs can be tested in
single-exponential fixed-parameter tractable time. Finally, we present how the
new approach can be used to obtain exact fixed-parameter tractable algorithms
for cutwidth and pathwidth, with single- exponential running time dependency on
the optimal width.
