Triangle packing in (sparse) tournaments: approximation and kernelization

2017/07/13 by Bessy, Stéphane, Bougeret, Marin, Thiebaut, Jocelyn · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1707.04220

Abstract

Given a tournament T and a positive integer k, the C₃-Pakcing-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₃-Pakcing-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₃-Pakcing-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₃-Pakcing-T when restricted to sparse instances. On the negative size, we show that C₃-Pakcing-T does not admit a kernel of (total bit) size O(k^2-ε) unless NP is a subset of coNP / Poly. The existence of a kernel in O(k) vertices for C₃-Pakcing-T remains an open question.

Cited by

• The structure of Δ(1, 2, 2)-free tournaments

Related

• (Arc-disjoint) cycle packing in tournament: classical and parameterized complexity
• A 7/3-Approximation for Feedback Vertex Sets in Tournaments
• An Almost Quadratic Vertex Kernel for Subset Feedback Arc Set in Tournaments
• Kernels for Feedback Arc Set In Tournaments
• Quick-Sort Style Approximation Algorithms for Generalizations of Feedback Vertex Set in Tournaments