2026-07-20T11:02:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2305 2024-03-06T10:33:15Z ddc:004 open_access

Kernels for Feedback Arc Set In Tournaments Bessy, Stéphane Fomin, Fedor V. Gaspers, Serge Paul, Christophe Perez, Anthony Saurabh, Saket Thomassé, Stéphan Parameterized complexity kernels tournaments 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stéphane Bessy and Fedor V. Fomin and Serge Gaspers and Christophe Paul and Anthony Perez and Saket Saurabh and Stéphan Thomassé 2009 Is Part Of LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2009.2305 urn:nbn:de:0030-drops-23055 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2305 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode