Kernels for Feedback Arc Set In Tournaments

pages

English

Documents

Écrit par
Stephane Bessy

Publié par
pefav

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

English

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Nombre de lectures

Langue

English

Kernels for Feedback Arc Set In Tournaments Stephane Bessy? Fedor V. Fomin† Serge Gaspers‡ Christophe Paul? Anthony Perez? Saket Saurabh† Stephan Thomasse? 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. 1 Introduction Given a directed graph G = (V,A) 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 directed graph.

let d?

parameterized complexity

time algorithm

minimum sized feedback

feedback arc

using only

algorithm solves

polynomial time

Voir

Publié par

pefav

Nombre de lectures

Langue

English

Parameterized complexity Time complexity

KernelsforFeedbackArcSetInTournamentsSte´phaneBessy∗FedorV.Fomin†SergeGaspers‡ChristophePaul∗AnthonyPerez∗SaketSaurabh†Ste´phanThomasse´∗AbstractAtournamentT=(V,A)isadirectedgraphinwhichthereisexactlyonearcbetweeneverypairofdistinctvertices.Givenadigraphonnverticesandanintegerparameterk,theFeedbackArcSetproblemaskswhetherthegivendigraphhasasetofkarcswhoseremovalresultsinanacyclicdigraph.TheFeedbackArcSetproblemrestrictedtotournamentsisknownasthek-FeedbackArcSetinTournaments(k-FAST)problem.Inthispaperweobtainalinearvertexkernelfork-FAST.Thatis,wegiveapolynomialtimealgorithmwhichgivenaninputinstanceTtok-FASTobtainsanequivalentinstanceT0onO(k)vertices.Infact,givenanyﬁxed>0,thekernelizedinstancehasatmost(2+)kvertices.OurresultimprovesthepreviousknownboundofO(k2)onthekernelsizefork-FAST.Ourkernelizationalgorithmsolvestheproblemonasubclassoftournamentsinpolynomialtimeandusesaknownpolynomialtimeapproximationschemefork-.TSAF1IntroductionGivenadirectedgraphG=(V,A)onnverticesandanintegerparameterk,theFeedbackArcSetproblemaskswhetherthegivendigraphhasasetofkarcswhoseremovalresultsinanacyclicdirectedgraph.Inthispaper,weconsiderthisprobleminaspecialclassofdirectedgraphs,tournaments.AtournamentT=(V,A)isadirectedgraphinwhichthereisexactlyonedirectedarcbetweeneverypairofvertices.Moreformallytheproblemweconsiderisdeﬁnedasfollows.k-FeedbackArcSetinTournaments(k-FAST):GivenatournamentT=(V,A)andapositiveintegerk,doesthereexistasubsetF⊆AofatmostkarcswhoseremovalmakesTacyclic.Intheweightedversionofk-FAST,wearealsogivenintegerweights(eachweightisatleastone)onthearcsandtheobjectiveistoﬁndafeedbackarcsetofweightatmostk.Thisproblemiscalledk-WeightedFeedbackArcSetinTournaments(k-WFAST).∗LIRMM–Universite´deMontpellier2,CNRS,161rueAda,34392Montpellier,France.{bessy|paul|perez|thomasse}@lirmm.fr†DepartmentofInformatics,UniversityofBergen,N-5020Bergen,Norway.{fedor.fomin|saket.saurabh}@ii.uib.no‡CentrodeModelamientoMatema´tico,UniversidaddeChile,8370459SantiagodeChile.sgaspers@dim.uchile.cl1

Voir