 |
HAL-LIRMM - Open Archive |  |
Conference papers
Kernels for Feedback Arc Set In Tournaments
Abstract : A tournament T = (V , A) is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on n vertices and an integer parameter k, the Feedback Arc Set problem asks whether the given digraph has a set of k arcs whose removal results in an acyclic digraph. The Feedback Arc Set problem restricted to tournaments is known as the k-Feedback Arc Set in Tournaments (k-FAST) problem. In this paper we obtain a linear vertex kernel for k-FAST. That is, we give a polynomial time algorithm which given an input instance T to k-FAST obtains an equivalent instance T ′ on O(k) vertices. In fact, given any fixed ϵ > 0, the kernelized instance has at most (2 + ϵ)k vertices. Our result improves the previous known bound of O(k2 ) on the kernel size for k-FAST. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for k- FAST.
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00432668
Contributor : Christophe Paul <>
Submitted on : Monday, November 16, 2009 - 8:19:03 PM
Last modification on : Friday, November 20, 2020 - 4:22:03 PM
Contributor : Christophe Paul <>
Submitted on : Monday, November 16, 2009 - 8:19:03 PM
Last modification on : Friday, November 20, 2020 - 4:22:03 PM