Triangle packing in (sparse) tournaments: approximation and kernelization

DOI10.4230/LIPICS.ESA.2017.14zbMATH Open1442.68160arXiv1707.04220OpenAlexW2963920736MaRDI QIDQ5111699FDOQ5111699

Marin Bougeret, Jocelyn Thiebaut, Stéphane Bessy

Publication date: 27 May 2020

Abstract: Given a tournament T and a positive integer k, the C_3-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_3-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_3-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_3-Pakcing-T when restricted to sparse instances. On the negative size, we show that C_3-Pakcing-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-Pakcing-T remains an open question.

Full work available at URL: https://arxiv.org/abs/1707.04220

Recommendations

• Packing edge-disjoint triangles in regular and almost regular tournaments
• A randomized approximation algorithm for metric triangle packing
• A randomized approximation algorithm for metric triangle packing
• Towards optimal kernel for edge-disjoint triangle packing
• Algorithms – ESA 2004
• An approximation algorithm for maximum triangle packing
• An improved randomized approximation algorithm for maximum triangle packing
• An Improved Randomized Approximation Algorithm for Maximum Triangle Packing
• Packing triangles in regular tournaments
• An improved kernel for planar vertex-disjoint triangle packing

zbMATH Keywords

approximation algorithmsfeedback arc setparameterized algorithmstournament triangle packing

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Properties of vertex packing and independence system polyhedra
• Title not available (Why is that?)
• A Problem Kernelization for Graph Packing
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Min-Max Theorem on Feedback Vertex Sets
• A Quadratic Kernel for 3-Set Packing
• Title not available (Why is that?)
• Complementary cycles in regular bipartite tournaments: a proof of Manoussakis, Song and Zhang conjecture
• Sparsification Upper and Lower Bounds for Graphs Problems and Not-All-Equal SAT
• A 7/3-Approximation for Feedback Vertex Sets in Tournaments

Cited In (5)

• A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing
• Packing Arc-Disjoint Cycles in Tournaments
• Tournaments and Semicomplete Digraphs
• Degreewidth: A New Parameter for Solving Problems on Tournaments
• Packing arc-disjoint cycles in tournaments

This page was built for publication: Triangle packing in (sparse) tournaments: approximation and kernelization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111699)