License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2017.14
URN: urn:nbn:de:0030-drops-78622
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7862/
Go to the corresponding LIPIcs Volume Portal

Bessy, Stéphane ; Bougeret, Marin ; Thiebaut, Jocelyn

Triangle Packing in (Sparse) Tournaments: Approximation and Kernelization

pdf-format:
LIPIcs-ESA-2017-14.pdf (0.7 MB)

Abstract

Given a tournament T and a positive integer k, the C_3-Packing-T 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 is a subset of coNP / Poly. The existence of a kernel in O(k) vertices for C_3-Packing-T remains an open question.

BibTeX - Entry

@InProceedings{bessy_et_al:LIPIcs:2017:7862,
  author =	{St{\'e}phane Bessy and Marin Bougeret and Jocelyn Thiebaut},
  title =	{{Triangle Packing in (Sparse) Tournaments: Approximation and Kernelization}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{14:1--14:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7862},
  URN =		{urn:nbn:de:0030-drops-78622},
  doi =		{10.4230/LIPIcs.ESA.2017.14},
  annote =	{Keywords: Tournament Triangle packing, Feedback arc set, Approximation algorithms, Parameterized algorithms}
}

Keywords: Tournament Triangle packing, Feedback arc set, Approximation algorithms, Parameterized algorithms
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI