CS Paper Radar

FPT Isomorphism Test for $F$-Free Tournaments

Daniel Neuen

cs.DS cs.DM ·submitted 2026-09-21 16:01 UTC · v1

Abstract

We show that isomorphism of $F$-free tournaments can be solved in FPT time $f(k) \cdot n^{O(1)}$, where $k$ denotes the size of $F$, and $n$ denotes the size of the input tournaments. Our result extends on a previous FPT isomorphism test for tournaments of bounded twin-width [Grohe, Neuen 2024], as well as XP isomorphism tests parameterized by the VC dimension or the chromatic number [Raßmann, Schweitzer 2026]. It also implies that every non-trivial hereditary class of tournaments admits a polynomial-time isomorphism test. Our algorithm builds on a novel combination of spectral, geometric, combinatorial and group-theoretic tools.

Comment
17 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Isomorphism of tournaments with bounded VC dimension

cs.DS cs.DMmath.CO ·2026-08-14 ·Simon Raßmann, Pascal Schweitzer
similarity 0.78
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

Clique Number of Tournaments II

cs.DM math.CO ·2026-09-07 ·Guillaume Aubian, Samuel Coulomb
theory similarity 0.67
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.

0.06

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.67
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

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.66
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

A New Upper Bound for 7-Universal Tournaments

cs.DM math.CO ·2026-09-24 ·Harshit Verma
theory similarity 0.65
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

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.65
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

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.62
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

Characterizing Necessary Losers to Explain Tournaments Solutions

cs.AI ·2026-08-24 ·Contet Clément, Umberto Grandi, Jérôme Mengin
published similarity 0.62
Abstract · This paper is the extended version of Contet, Grandi, Mengin. Characterizing Necessary Losers to Explain Tournaments Losers. In: Proceedings…

We study the problem of formally explaining why a candidate was not selected by a given tournament rule, by identifying sub-tournaments in which the candidate loses independently of how the rest of the tournament is completed. We define destructive minimal supports as any minimal sub-tournament satisfying this property, which in formal explainable artificial intelligence corresponds to abductive explanations for the question "Why does the loser lose the tournament?". For six common tournament solutions (maximin, uncovered set and its weighted variant, top cycle, Copeland, and Borda) we provide characterizations of when a candidate is either a necessary loser or a possible winner, we determine the size of the smallest destructive minimal supports, complemented by polynomial-time algorithms for their computation except for the case of Borda and Copeland rules which we conjecture to also be polynomial.

0.42