# 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].

##### MSC:
 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: