Bessy, Stéphane ;
Fomin, Fedor V. ;
Gaspers, Serge ;
Paul, Christophe ;
Perez, Anthony ;
Saurabh, Saket ;
Thomassé, Stéphan
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 {\sc Feedback Arc Set} problem asks whether thegiven digraph has a set of $k$ arcs whose removal results in an acyclicdigraph. The {\sc Feedback Arc Set} problem restricted to tournaments is knownas the {\sc $k$Feedback Arc Set in Tournaments ($k$FAST)} problem. In thispaper we obtain a linear vertex kernel for \FAST{}. That is, we give apolynomial time algorithm which given an input instance $T$ to \FAST{} obtains an equivalent instance $T'$ on $O(k)$ vertices. In fact, given any fixed $\epsilon > 0$, the kernelized instance has at most $(2 + \epsilon)k$ vertices.Our result improves the previous known bound of $O(k^2)$ on the kernel size for\FAST{}. Our kernelization algorithm solves the problem on a subclass of
tournaments in polynomial time and uses a known polynomial time approximation
scheme for \FAST.
BibTeX  Entry
@InProceedings{bessy_et_al:LIPIcs:2009:2305,
author = {St{\'e}phane Bessy and Fedor V. Fomin and Serge Gaspers and Christophe Paul and Anthony Perez and Saket Saurabh and St{\'e}phan Thomass{\'e}},
title = {{Kernels for Feedback Arc Set In Tournaments}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {3747},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897132},
ISSN = {18688969},
year = {2009},
volume = {4},
editor = {Ravi Kannan and K. Narayan Kumar},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2305},
URN = {urn:nbn:de:0030drops23055},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2009.2305},
annote = {Keywords: Parameterized complexity, kernels, tournaments}
}
Keywords: 

Parameterized complexity, kernels, tournaments 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

Issue date: 

2009 
Date of publication: 

14.12.2009 