Paper Info
Title
(Arc-disjoint) cycle packing in tournament: classical and parameterized complexity.
Abstract
Given a tournament $T$, the problem MaxCT consists of finding a maximum (arc-disjoint) cycle packing of $T$. the same way, MaxTT corresponds to the specific case where the collection of cycles are triangles (i.e. directed 3-cycles). Although MaxCT can be seen as the LP dual of minimum feedback arc set in tournaments which have been widely studied, surprisingly no algorithmic results seem to exist concerning the former. In this paper, we prove the NP-hardness of both MaxCT and MaxTT. We also show that deciding if a tournament has a cycle packing and a feedback arc set with the same size is an NP-complete problem. light of this, we show that MaxTT admits a vertex linear-kernel when parameterized with the size of the solution. Finally, we provide polynomial algorithms for MaxTT and MaxCT when the tournament is sparse, that is when it admits a FAS which is a matching.
Year
Venue
Field
2018
arXiv: Discrete Mathematics
Discrete mathematics,Parameterized complexity,Combinatorics,Tournament,Arc (geometry),Disjoint sets,Vertex (geometry),Polynomial algorithm,Mathematics,Feedback arc set
DocType
Volume
Citations 
Journal
abs/1802.06669
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Stéphane Bessy111719.68
Marin Bougeret211313.35
Jocelyn Thiebaut300.34