Triangle and cycle packing in tournaments: complexity and algorithms

Prelegent(ci)

Stéphane Bessy

Afiliacja

LIRMM Montpellier

Termin

17 października 2019 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

Given a tournament T and a positive integer k, we study different question dealing with packing (oriented) cycles in tournament: does T contain k vertex-disjoint cycles (k-VCT)? k arc-disjoint cycles (k-ACT)? k-arc-disjoint triangles (k-ATT)?, where a triangle is an oriented 3-cycle. These problems are dual problems in tournaments of the classical minimal feedback set problems. However, surprisingly, they did not receive a lot of attention in the literature. I will present the results we have obtained on these problems. On the negative side, we show that all of three are NP-complete. More precisely, k-VTT is NPC and does not admit a PTAS unless P=NP. k-ACT and k-ATT are also NPC, with no PTAS, and even if we restrict the considered instances to sparse tournaments, that is tournaments with a feedback arc set (FAS) being a matching. On the positive side, we provide a 2^O(k log k) FPT algorithm for k-ACT, a 2^O(k) FPT algorithm for k-ATT and linear kernel for both problems. We also obtained some interesting approximation and FPT algorithms on the classe of sparse tournaments. Joint work with M.Bougert, J.Thiebaut and R. Krithika, A. Sahu, S. Saurabh, J. Thiebaut, M. Zehavi

---