Skip to Main content Skip to Navigation
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.
Document type :
Conference papers
Complete list of metadata
Contributor : Christophe Paul <>
Submitted on : Monday, November 16, 2009 - 8:19:03 PM
Last modification on : Friday, November 20, 2020 - 4:22:03 PM


  • HAL Id : lirmm-00432668, version 1



Stéphane Bessy, Fedor V. Fomin, Serge Gaspers, Christophe Paul, Anthony Perez, et al.. Kernels for Feedback Arc Set In Tournaments. FSTTCS'09: Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2009, IIT Kanpur, India. pp.N/A. ⟨lirmm-00432668⟩



Record views