December 13th, 2017

Shaving the poly(n) for Feedback Vertex Set on directed graphs


In the decision version of the classic Feedback Vertex Set problem on directed graphs, the input is a digraph D and an integer k and the objective is to check whether D has a set of at most k vertices which intersect every directed cycle. While clearly polynomial time solvable for every fixed value of k, it is NP-complete when k is part of the input and a long standing open problem in the area of fixed-parameter tractability was whether there is a polynomial time algorithm for every fixed value of k, but such that the exponent of the input size is independent of k. In other words, for some computable function f, can we provide an algorithm whose running time is bounded by $f(k) n^c$, where n is the number of vertices of D and c is a constant independent of k.

Chen et al. [JACM 2008] answered this question with an $O( 4^k k! k^4 mn)$ algorithm, where m is the number of arcs/edges of D. This has remained the best FPT algorithm for this problem and the two main questions that arose from their work are : 

(a) Can the k! term be asymptotically improved upon (perhaps at the cost of a much worse polynomial dependence on m and n)?

(b) Can the multiplicative mn term be improved to m+n (perhaps at the cost of a much worse dependence on k)?

While the first question still remains open, the second question was recently resolved by a joint paper with Daniel Lokshtanov and Saket Saurabh (SODA 2018). In this paper, we give an $O( 4^kk!k^5(m+n))$ algorithm for the problem. In other words, one can achieve a linear dependence on the size of D at a slightly worse dependence on k. In fact, the dependence on k is asymptotically the same as that of the algorithm of Chen et al. and so is essentially the current best known FPT algorithm for this problem.