zbMATH — the first resource for mathematics

Faster exact and parameterized algorithm for feedback vertex set in tournaments. (English) Zbl 1388.68324
Ollinger, Nicolas (ed.) et al., 33rd symposium on theoretical aspects of computer science, STACS 2016, Orléans, France, February 17–20, 2016. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-001-9). LIPIcs – Leibniz International Proceedings in Informatics 47, Article 49, 13 p. (2016).
Summary: A tournament is a directed graph \(T\) such that every pair of vertices is connected by an arc. A feedback vertex set is a set \(S\) of vertices in \(T\) such that \(T-S\) is acyclic. In this article we consider the Feedback Vertex Set problem in tournaments. Here the input is a tournament \(T\) and an integer \(k\), and the task is to determine whether \(T\) has a feedback vertex set of size at most \(k\). We give a new algorithm for Feedback Vertex Set In Tournaments. The running time of our algorithm is upper-bounded by \(O(1.6181^k+n^{O(1)})\) and by \(O(1.466^n)\). Thus our algorithm simultaneously improves over the fastest known parameterized algorithm for the problem by M. Dom et al. [Lect. Notes Comput. Sci. 3998, 320–331 (2006; Zbl 1183.68419); J. Discrete Algorithms 8, No. 1, 76–86 (2010; Zbl 1191.68349)] running in time \(O(2^kk^{O(1)}+n^{O(1)})\), and the fastest known exact exponential-time algorithm by S. Gaspers and M. Mnich [J. Graph Theory 72, No. 1–2, 72–89 (2013; Zbl 1259.05070)] with running time \(O(1.674^n)\). On the way to proving our main result we prove a strengthening of a special case of a graph partitioning theorem due to B. Bollobás and A. D. Scott [J. Graph Theory 46, No. 2, 131–143 (2004; Zbl 1048.05067)]. In particular we show that the vertices of any undirected \(m\)-edge graph of maximum degree \(d\) can be colored white or black in such a way that for each of the two colors, the number of edges with both endpoints of that color is between \(m/4-d/2\) and \(m/4+d/2\).
For the entire collection see [Zbl 1338.68009].

68W40 Analysis of algorithms
05C15 Coloring of graphs and hypergraphs
05C20 Directed graphs (digraphs), tournaments
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: DOI