zbMATH — the first resource for mathematics

Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph. (English) Zbl 1395.68359
Bodlaender, Hans L. (ed.) et al., Algorithms – ESA 2013. 21st annual European symposium, Sophia Antipolis, France, September 2–4, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-40449-8/pbk). Lecture Notes in Computer Science 8125, 505-516 (2013).
Summary: Cutwidth of a digraph is a width measure introduced by M. Chudnovsky et al. [J. Comb. Theory, Ser. B 102, No. 1, 93–101 (2012; Zbl 1241.05040)] in connection with development of a structural theory for tournaments, or more generally, for semi-complete digraphs. In this paper we provide an algorithm with running time \(2^{O(\sqrt{k\log k})}\cdot n^{O(1)}\) that tests whether the cutwidth of a given \(n\)-vertex semi-complete digraph is at most \(k\), improving upon the currently fastest algorithm of the second author [LIPICS – Leibniz Int. Proc. Inform. 20, 197–208 (2013; Zbl 1354.68302)] that works in \(2^{O(k)}\cdot n ^{2}\) time. As a byproduct, we obtain a new algorithm for Feedback Arc Set in tournaments (FAST) with running time \(2^{c\sqrt{k}}\cdot n^{O(1)}\), where \(c=\frac{2\pi}{\sqrt{3}\cdot \ln 2}\leq 5.24\), that is simpler than the algorithms of U. Feige [“Faster FAST (feedback arc set in tournaments)”, Preprint, arXiv:0911.5094] and of M. Karpinski and W. Schudy [Lect. Notes Comput. Sci. 6506, 3–14 (2010; Zbl 1310.68272)], both also working in \(2^{O(\sqrt{k})}\cdot n^{O(1)}\) time. Our techniques can be applied also to other layout problems on semi-complete digraphs. We show that the Optimal Linear Arrangement problem, a close relative of Feedback Arc Set, can be solved in \(2^{O(k^{\frac13}\cdot\sqrt{\log k})}\cdot n^{O(1)}\) time, where \(k\) is the target cost of the ordering.
For the entire collection see [Zbl 1270.68017].

68W40 Analysis of algorithms
05C20 Directed graphs (digraphs), tournaments
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI