FPT Isomorphism Test for F-Free Tournaments

Daniel Neuen

In the authors' words

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{\ss}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.

Main resultThe abstract does not state a limitation.

FPT Isomorphism Test for F-Free Tournaments

In the authors' words

More on Algorithms & complexity that day

Smoothed Analysis of Inconsistent A*

Hardness of Online Directed Steiner Network

Single-Pass Estimation of the Clustering Coefficient Distribution in Graph Streams

Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time

Parameter-Free Triangle Counting

FPT Isomorphism Test for $F$ -Free Tournaments