Kernels for Feedback Arc Set In Tournaments

Stéphane Bessy 1 Fedor Fomin 2 Serge Gaspers 1 Christophe Paul 1 Anthony Perez 3 Saket Saurabh 2 Stéphan Thomassé 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 Department of Informatics
3 LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Type de document :
Communication dans un congrès
FSTTCS'09: Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2009, IIT Kanpur, India. pp.N/A, 2009, Leibniz International Proceedings in Informatics. 〈http://www.fsttcs.org/archives/2009/〉
Liste complète des métadonnées
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00432668
Contributeur : Christophe Paul <>
Soumis le : lundi 16 novembre 2009 - 20:19:03
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00432668, version 1

Collections

ALGCO | LIRMM | MIPS | TDS-MACS | UNIV-MONTPELLIER

Citation

Stéphane Bessy, Fedor 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, 2009, Leibniz International Proceedings in Informatics. 〈http://www.fsttcs.org/archives/2009/〉. 〈lirmm-00432668〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

92

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD