Triangle packing in (sparse) tournaments: approximation and kernelization *

Stéphane Bessy 1 Marin Bougeret 1 Jocelyn Thiebaut 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Type de document :
Communication dans un congrès
Kirk Pruhs; Christian Sohler. ESA: European Symposium on Algorithms, Sep 2017, Vienne, Austria. 25th Annual European Symposium on Algorithms, pp.1-23, 2017, Leibniz International Proceedings in Informatics. 〈http://esa-symposium.org〉. 〈10.4230/LIPIcs.ESA.2017〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01550313
Contributeur : Marin Bougeret <>
Soumis le : jeudi 29 juin 2017 - 14:45:19
Dernière modification le : jeudi 19 juillet 2018 - 11:54:04
Document(s) archivé(s) le : jeudi 18 janvier 2018 - 02:49:16

Fichier

triangle_packing_hal.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Citation

Stéphane Bessy, Marin Bougeret, Jocelyn Thiebaut. Triangle packing in (sparse) tournaments: approximation and kernelization *. Kirk Pruhs; Christian Sohler. ESA: European Symposium on Algorithms, Sep 2017, Vienne, Austria. 25th Annual European Symposium on Algorithms, pp.1-23, 2017, Leibniz International Proceedings in Informatics. 〈http://esa-symposium.org〉. 〈10.4230/LIPIcs.ESA.2017〉. 〈lirmm-01550313〉

Partager

Métriques

Consultations de la notice

169

Téléchargements de fichiers

133