Deciding directed clique number in tournaments is np complete
Clique Number of Tournaments II
Discrete Mathematics
Summary
This paper studies a special math problem involving tournaments, which are games where every player competes against every other player. The authors show that figuring out a certain complexity measure called the directed clique number (a way to find tightly connected groups in these competitions) is very hard to compute—it belongs to a class of problems called NP-complete. However, they also provide an efficient method to distinguish simpler cases from very complex ones. Additionally, the authors explore related properties of tournaments, confirming some previous ideas and disproving others, deepening our understanding of these mathematical structures.
What this means in practice
- •For algorithm designers: Avoid attempting polynomial-time algorithms to decide directed clique number beyond trivial cases in tournaments, due to NP-completeness.
- •For network analysts: Use efficient algorithms to distinguish tournaments with small or very large directed clique numbers for analyzing hierarchical or competitive networks.
A theory result. No direct application yet.
Authors
Guillaume Aubian, Samuel Coulomb
Abstract
The directed clique number $\vecω(T)$ of a tournament $T$ is the minimum, over all orderings of the vertices of $T$, of the clique number of the graph whose edges are the arcs that point backward with respect to the ordering. In this paper, we prove that, for every integer $k \geq 3$, deciding whether $\vecω(T) \leq k$ is NP-complete. This answers a question of Nguyen, Scott, and Seymour, and contrasts with the classical undirected setting, where deciding whether $ω(G) \leq k$ is polynomial-time solvable for every fixed integer $k$. On the other hand, we give a polynomial-time algorithm distinguishing tournaments with $\vecω(T) \leq 2$ from those with $\vecω(T) > 100$. We also study the tournament analogue of the Gyárfás--Sumner conjecture. We construct new $\vecχ$-bounding tournaments and thereby prove a conjecture of Aboulker, Aubian, Charbit, and Lopes stating that every class of tournaments with bounded twin-width is $\vecχ$-bounded. We then exhibit new tournaments that are not $\vecχ$-bounding, disproving another conjecture of Aboulker, Aubian, Charbit, and Lopes, as well as two conjectures of Kim. Finally, we present infinite families of 3-$\vecω$-critical and 4-$\vecω$-critical tournaments.