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.
Type de document :
Article dans une revue
Journal of Computer and System Sciences, Elsevier, 2011, 77 (6), pp.1071-1078
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00738221
Contributeur : Stéphane Bessy <>
Soumis le : mercredi 3 octobre 2012 - 17:36:12
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : vendredi 4 janvier 2013 - 03:59:05

Fichier

fast.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00738221, version 1

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

149

Téléchargements de fichiers

228