CS Paper Radar

Clique Number of Tournaments II

Guillaume Aubian, Samuel Coulomb

cs.DM math.CO ·submitted 2026-09-07 13:35 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Crossing tournaments are polynomially $\vecχ$-bounded

cs.DM math.CO ·2026-08-10 ·Lila Crew, Xinyue Fan, Hidde Koerts, Benjamin Moore, Sophie Spirkl
similarity 0.81
Abstract

Given a tournament $T$, Aboulker, Aubian, Charbit, and Lopes (2023) defined its clique number $\vecω(T)$ as the minimum clique number of a backedge graph of $T$, and raised the question: Which classes of tournaments are polynomially $\vecχ$-bounded? Aboulker, Duron, Jacob, Kimbrough, Thomassé, and this work's authors (2026) showed that this holds for classes of tournaments whose arc sets may be written as the union of a bounded number of comparability digraphs. What about classes of tournaments that do not admit such a decomposition? The crossing tournaments of Nguyen, Scott, and Seymour (2025) are an example of such a class, as shown in the aforementioned 2026 work; we show that nonetheless crossing tournaments are polynomially $\vecχ$-bounded by adapting a method of Davies and McCarty (2021) and Davies (2022). We additionally show that we cannot extend this result for crossing tournaments to tournaments with chordal graphs as backedge graphs.

0.04

Digraphs of Large Girth and Dichromatic Number in Tournaments with Large Dichromatic Number

cs.DM math.CO ·2026-09-18 ·Pierre Charbit, Samuel Coulomb
theory similarity 0.73
Abstract

In the 1960s, Erdős and Hajnal conjectured that every graph with sufficiently large chromatic number contains a subgraph of large girth (size of a smallest cycle) and large chromatic number. In this paper, we prove that every tournament with sufficiently large dichromatic number contains a subdigraph of large digirth (size of a smallest directed cycle) and large dichromatic number. We investigate the same statement when replacing digirth by girth (of the underlying graph). We show that it implies the conjecture of Erdős and Hajnal, and prove it for a particular family of tournaments.

0.07

A Deterministic $(2+\varepsilon)$-Approximation for Weighted Feedback Vertex Set in Tournaments

cs.DS ·2026-09-14 ·Hanqing Li, Zihan Wu
theory similarity 0.71
Abstract · 8 pages, no figures

We study the weighted feedback vertex set problem in tournaments. For every fixed integer $k\geq 2$, we give a deterministic $(2+1/k)$-approximation algorithm with running time $n^{2^{O(k)}}$, apart from polynomial dependence on the encoding length of the weights. Consequently, for every fixed $\varepsilon>0$, weighted feedback vertex set in tournaments has a deterministic $(2+\varepsilon)$-approximation running in time $n^{2^{O(1/\varepsilon)}}$. The algorithm combines two ingredients. When the triangle graph of the tournament has bounded clique number, a chain decomposition of its transitive complement yields an exact dynamic program for a maximum-weight transitive subtournament. When the clique number is large, a structural theorem for triangle graphs supplies a constant-size strongly good cost vector. A local-ratio reduction with this cost vector gives the claimed guarantee. As a by-product, the dynamic program solves weighted feedback vertex set exactly in $\mathcal B_7$-free tournaments in time $O(n^7)$, where $\mathcal B_7$ is the family of seven-vertex tournaments with feedback vertex set number at least three.

0.27

Isomorphism of tournaments with bounded VC dimension

cs.DS cs.DMmath.CO ·2026-08-14 ·Simon Raßmann, Pascal Schweitzer
similarity 0.71
Abstract

The tournament isomorphism problem is one of the two fundamental bottlenecks to designing better algorithms for the graph isomorphism problem. Though the problem has been investigated for more than five decades, compared to graphs, there are only very few results on the isomorphism problem of tournaments. For most classes of tournaments neither hardness nor polynomial-time solvability is known. Tournaments of bounded VC dimension are such a class for which no results are available, even though the VC dimension is arguably one of the most robust and central notions of combinatorial tameness. Resolving an open problem of Neuen and Grohe, we show that the isomorphism problem for tournaments of VC dimension $d$ can be decided in time $n^{O(d\log d)}$. Consequently, automorphism groups of tournaments of bounded VC dimension can be computed in polynomial time. To this end, we develop a new method to isomorphism-invariantly decompose tournaments. To facilitate recursion, we introduce the notion of a patched tournament and analyze bounded VC dimension in patched tournaments. We design a recursive algorithm that balances the size of the decomposed pieces against their number and makes use of the structure of near twins. In an orthogonal direction, it is known that a hereditary class of tournaments has unbounded VC dimension if and only if it contains all 2-colorable tournaments. As a second result, we show that also this class does not form an obstruction towards polynomial-time isomorphism testing and indeed show that isomorphism of tournaments of bounded chromatic number is polynomial-time decidable.

0.32

A New Upper Bound for 7-Universal Tournaments

cs.DM math.CO ·2026-09-24 ·Harshit Verma
theory similarity 0.70
Abstract

A tournament is $k$-universal if it contains every tournament on $k$ vertices as a subtournament. We give a 7-universal tournament on 14 vertices, improving the upper bound of 15 due to Zhang and Szeider. Together with their lower bound, it follows that the smallest 7-universal tournament has 13 or 14 vertices.

0.09

Directed Cut-Query Complexity of Finding a King

cs.CC math.CO ·2026-10-29 ·Ziad Ismaili Alaoui, Oded Lachish, Nikhil S. Mande
theory similarity 0.69
Abstract

A king in a tournament is a vertex from which every other vertex is reachable by a directed path of length at most two. We study the deterministic query complexity of finding a king when a query specifies a set of vertices and returns the number of edges directed from that set to its complement. We prove that this complexity is $Θ(n)$ for $n$-vertex tournaments. To show this, we first show that every correct deterministic algorithm in this model must output a maximum-outdegree vertex, even though a king need not have maximum outdegree. We then give an adversary whose answers, after too few queries, remain consistent with a tournament in which the algorithm's output does not have maximum outdegree.

0.34

Tournaments not inducible by five voters

cs.DM ·2026-09-12 ·Leonid Chindelevitch, Ararat Harutyunyan
theory similarity 0.69
Abstract · 31 pages, 4 figures; v2: upper bound improved to $N(5) \leq 22$ (v1: $\leq 23$), refuting v1's conjecture $N(5) = 23$. Companion paper: arXi…

How many members must a committee have before its pairwise majorities can express any collective preference? With enough voters every pattern of pairwise majorities, or tournament, can arise, but a committee of $k$ voters produces only some; for odd $k$, let $N(k)$ be the least number of alternatives on which some tournament arises from no $k$ voters. Only $N(3) = 8$ is known; for five voters our companion paper gave $12 \le N(5) \le 38$ and the first explicit example of moderate size, on 43 vertices. We show $13 \le N(5) \le 22$. The upper bound comes from nine tournaments on 22 vertices that five voters cannot produce: eight one-vertex deletions of doubly regular tournaments on 23 vertices, including every deletion of one of them, and one arc reversal. The Paley tournament on 23 vertices, which Bachmeier et al. (2019) left open after six weeks of SAT solving, is beyond five voters, and so is every other doubly regular tournament on 23 vertices. The lower bound comes from an analysis of all tournaments on 12 vertices. Both doubly regular tournaments on 19 vertices, the Paley tournament and one other, arise from five voters, but not with unit margin, that is, not with every majority carried by three votes to two. The method is a search that places one alternative at a time and exploits the tournament's symmetries; four of the negative results are certified by machine-checkable proofs, and all results are reproducible from a public repository.

0.21

The Tournament Equilibrium Set Is PSPACE-Complete, Even under Hereditary Uniqueness

cs.GT cs.CC ·2026-11-12 ·Ethan Dickey, Athina Terzoglou
theory similarity 0.69
Abstract · 51 pages, 11 figures

The tournament equilibrium set (TEQ), proposed by Schwartz in 1990, is a classical voting rule based on pairwise majority comparisons. Its definition is recursive: an alternative is judged by the alternatives that beat it, called its dominators, and by which of those dominators TEQ itself selects. Deciding whether a given alternative belongs to TEQ was known to be NP-hard and to lie in PSPACE. We close this gap by proving that the problem is PSPACE-complete. To our knowledge, this is the first PSPACE-completeness result for membership in a tournament solution. The hardness persists even when every nonempty subtournament has a unique minimal retentive set, the property conjectured by Schwartz to hold for all tournaments. Moreover, every such subtournament in our hard instances contains an alternative with at most three dominators. We prove that a single alternative with at most four dominators suffices both to guarantee uniqueness and to find a TEQ winner in $O(N^2)$ time. Thus, on our hard instances, finding one winner is efficient even though recognizing a specified winner is PSPACE-complete. We also study how the complexity changes with the dominator bound. If every nonempty subtournament has an alternative with at most one dominator, the entire TEQ can be computed in quadratic time; allowing two dominators makes membership NP-hard. Under the same condition with four dominators, all $t$ winners can be computed in $O(2^t N^2)$ time, where $N$ is the number of alternatives.

0.24