Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Tournaments

الأصل · EN

A tournament is a directed graph T such that every pair of vertices are 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 input is a tournament T and 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.618ᵏ + nᵒ⁽¹⁾) and by O(1.46ⁿ). Thus our algorithm simultaneously improves over the fastest known parameterized algorithm for the problem by Dom et al. running in time O(2ᵏkᵒ⁽¹⁾ + nᵒ⁽¹⁾), and the fastest known exact exponential time algorithm by Gaspers and Mnich with running time O(1.674ⁿ). On the way to prove our main result we prove a new partitioning theorem for undirected graphs. 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/4.