zbMATH — the first resource for mathematics

Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings. (English) Zbl 1354.68302
Portier, Natacha (ed.) et al., 30th international symposium on theoretical aspects of computer science, STACS’ 13, Kiel, Germany, February 27 – March 2, 2013. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-50-7). LIPIcs – Leibniz International Proceedings in Informatics 20, 197-208 (2013).
Summary: 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 M. Chudnovsky, A. Fradkin, I. Kim, A. Scott, and P. Seymour. 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 [M. Chudnovsky et al., J. Comb. Theory, Ser. B 102, No. 1, 93–101 (2012; Zbl 1241.05040); A. Fradkin and P. Seymour, J. Comb. Theory, Ser. B 103, No. 3, 374–384 (2013; Zbl 1301.05148)] 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(\mathrm{OPT})\)-approximation in fixed-parameter tractable time [F. V. Fomin and the author, “Jungles, bundles, and fixed parameter tractability”, in: Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 396–413 (2013; doi:10.1137/1.9781611973105.29)] 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.
For the entire collection see [Zbl 1280.68037].

68W25 Approximation algorithms
05C20 Directed graphs (digraphs), tournaments
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI