Abstract | ||
---|---|---|
Given a tournament T and a positive integer k, the C_3-Packing-T problem asks if there exists a least k (vertex-)disjoint directed 3-cycles in T. This is the dual problem in tournaments of the classical minimal feedback vertex set problem. Surprisingly C_3-Packing-T did not receive a lot of attention in the literature. We show that it does not admit a PTAS unless P=NP, even if we restrict the considered instances to sparse tournaments, that is tournaments with a feedback arc set (FAS) being a matching. Focusing on sparse tournaments we provide a (1+ 6/(c−1)) approximation algorithm for sparse tournaments having a linear representation where all the backward arcs have length at least c. Concerning kernelization, we show that C_3-Packing-T admits a kernel with O(m) vertices, where m is the size of a given feedback arc set. In particular, we derive a O(k) vertices kernel for C_3-Packing-T when restricted to sparse instances. On the negative size, we show that C_3-Packing-T does not admit a kernel of (total bit) size O(k^{2−epsilon}) unless NP ⊆ coNP/Poly. The existence of a kernel in O(k) vertices for C_3-Packing-T remains an open question. |
Year | Venue | DocType |
---|---|---|
2017 | ESA | Conference |
Volume | Citations | PageRank |
abs/1707.04220 | 1 | 0.36 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Stéphane Bessy | 1 | 117 | 19.68 |
Marin Bougeret | 2 | 113 | 13.35 |
Jocelyn Thiebaut | 3 | 1 | 1.72 |