Sparse tournaments and their generalisation

The goal of this talk is to give a brief overview on the literature on sparse tournaments. A tournament is said to be sparse if there exists an ordering on its vertices such that the set of backward arcs (i.e., arcs with the head before the tail w.r.t the ordering) forms a matching.

To do so, we first study this property on tournaments in the context of cycle packing. Namely, we show on one hand that packing vertex-disjoint triangles is \(\mathsf{NP}\)-hard even restricted on sparse tournaments. On the other hand, we prove that while packing arc-disjoint cycles and packing arc-disjoint triangles are also \(\mathsf{NP}\)-hard in tournaments, it becomes polynomial time solvable when restricted to sparse tournaments. Similarly, we prove that Feedback Arc Set is polynomial in sparse tournaments while Feedback Vertex Set remains \(\mathsf{NP}\)-hard on this subclass of tournaments.

We then define a new parameter called degreewidth, and that can be seen as a generalisation of the notion of sparse tournaments. Formally, the degreewidth of a tournament corresponds to the minimum value \(k\) such that we can order its vertices in such a way that every vertex is incident to at most \(k\) backward arcs. Note that acyclic tournaments are exactly tournaments with degreewidth zero, and tournaments with degreewidth one are all sparse. Therefore, this parameter can be seen as a measure of how far the tournament is from being acyclic.

We study computational complexity of finding degreewidth. Namely, we show it is \(\mathsf{NP}\)-hard and complement this result with a \(3\)-approximation algorithm. Finally, we show that Dominating Set is \(\mathsf{FPT}\) parameterized by degreewidth.

This is joint work based on three different papers; two of them were written with Stéphane Bessy and Marin Bougeret while the third was written with Tom Davot, Lucas Isenmann and Sanjukta Roy.

Recording