Algorithms and Kernels for Feedback Set Problems in Generalizations of Tournaments

Abstract

In the DIRECTED FEEDBACK ARC (VERTEX) SET problem, we are given a digraph D with vertex set V(D) and arcs set A(D) and a positive integer k, and the question is whether there is a subset X of arcs (vertices) of size at most k such that the digraph obtained after deleting X from D is an acyclic digraph. In this paper we study these two problems in the realm of parametrized and kernelization complexity. More precisely, for these problems we give polynomial time algorithms, known as kernelization algorithms, on several digraph classes that given an instance (D, k) of the problem returns an equivalent instance (D′,k′) such that the size of D′ and k′ is at most k^O(1). We extend previous results for DIRECTED FEEDBACK ARC (VERTEX) SET on tournaments to much larger and well studied classes of digraphs. Specifically we obtain polynomial kernels for k-FVS on digraphs with bounded independence number, locally semicomplete digraphs and some totally Φ-decomposable digraphs, including quasi-transitive digraphs. We also obtain polynomial kernels for k-FAS on some totally Φ-decomposable digraphs, including quasi-transitive digraphs. Finally, we design a subexponential algorithm for k-FAS running in time 2^{O(k√(logk)c})n^d for constants c, d. on locally semicomplete digraphs.