Skip to Main content Skip to Navigation
Journal articles

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 T0 on O(k) vertices. In fact, given any xed > 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 :
Journal articles
Complete list of metadatas

Cited literature [30 references]  Display  Hide  Download
Contributor : Stéphane Bessy <>
Submitted on : Wednesday, October 3, 2012 - 5:36:12 PM
Last modification on : Tuesday, June 30, 2020 - 3:34:02 PM
Document(s) archivé(s) le : Friday, January 4, 2013 - 3:59:05 AM


Files produced by the author(s)


  • HAL Id : lirmm-00738221, version 1



Stéphane Bessy, Fedor Fomin, Serge Gaspers, Christophe Paul, Anthony Perez, et al.. Kernels for feedback arc set in tournaments. Journal of Computer and System Sciences, Elsevier, 2011, 77 (6), pp.1071-1078. ⟨lirmm-00738221⟩



Record views


Files downloads