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

For the entire collection see [Zbl 1338.68009].

##### MSC:

68W40 | Analysis of algorithms |

05C15 | Coloring of graphs and hypergraphs |

05C20 | Directed graphs (digraphs), tournaments |

05C85 | Graph algorithms (graph-theoretic aspects) |