Isomorphism test runs faster for restricted tournament graphs
FPT Isomorphism Test for $F$-Free Tournaments
Data Structures and AlgorithmsDiscrete Mathematics
Summary
Figuring out when two tournaments are essentially the same can be very hard. This paper shows that for tournaments avoiding certain smaller patterns, called F-free tournaments, there is a way to test if they are the same faster than usual, depending more on the size of the forbidden pattern than the tournament itself. The authors build on earlier work and combine many kinds of techniques like math and geometry. Their approach means many large classes of tournaments now have quicker tests to check if two are identical in structure.
What this means in practice
- •For graph algorithm engineers: Implement faster algorithms to determine if two large tournament-like data structures are equivalent when constraints exclude certain small patterns.
- •For network architects: Use improved isomorphism checks to identify equivalent network configurations modeled as tournaments under structural restrictions, aiding optimization.
A theory result. No direct application yet.
Authors
Daniel Neuen
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.