FPT Isomorphism Test for F-Free Tournaments
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "FPT Isomorphism Test for F-Free Tournaments".
Title and authors: Tom: So we're looking at this paper now, "FPT Isomorphism Test for F-Free Tournaments." It sounds like they're tackling the tournament isomorphism problem by generalizing what we already know about other graph classes.
Jane: Exactly. The title tells us it’s about finding an efficient way to check if two tournaments are isomorphic when you only care about tournaments that avoid a specific set of forbidden structures, F.
Lu: It's interesting because they're taking ideas from bounded twin-width and VC dimension classes and extending them to *any* non-trivial hereditary class of tournaments.
Meng: So, if I understand correctly, it means we can solve this isomorphism problem in fixed parameter tractable time when parameterized by the size of that forbidden set F.
Tom: Right. They claim they can do it in two to the power of k squared times n times some constant factor, where k is just the size of F. That's a significant improvement over what we had before for VC dimension or chromatic number constraints.
Jane: It’s huge because it implies that any class of tournaments you can define by forbidding certain induced subgraphs has this fixed parameter tractable isomorphism test.
Lu: And they build this up using a combination of tools—spectral, geometric, combinatorial, and group-theoretic methods—to find a specific structure in these F-free tournaments.
Meng: I wonder what that structure actually is. Is it something we can easily check on real data?
The paper's summary: Tom: Well, the paper outlines a two-phase approach to solving this isomorphism problem for F-free tournaments. First, they use combinatorial methods to find an isomorphism-invariant subset of edges that forms a connected subgraph with "near-bounded degree."
Jane: Near bounded degree is interesting. It sounds like they are trying to find a sparse structure that still captures enough information about the tournament's connectivity and local properties.
Lu: They achieve this by using the two dimensional Weisfeiler-Leman algorithm to color pairs of vertices in an isomorphism-invariant way, which then proves there exists a subset of two dimensional Weisfeiler-Leman colors that defines this subgraph.
Meng: So they use the 2D Weisfeiler-Leman algorithm, which is generally powerful for structural checks, to find this initial sparse graph <ref:2609.24804#pg1>. But what if that coloring doesn't capture enough information on its own?
Tom: That’s where the second phase comes in. They use group-theoretic methods to solve the isomorphism by exploiting that near bounded degree structure they found earlier.
Jane: So it’s a two-step process: first, find a sparse graph using combinatorial coloring, and then use group theory on that specific structure to determine the isomorphism.
Lu: The proof for this second phase relies on bounding the dimension of the eigenspace for the largest eigenvalue of a matrix associated with T. They show this dimension is bounded by two times k squared, where k is again the size of F.
Meng: Bounding that eigenspace dimension sounds like it’s crucial because it helps limit how many neighbors you need to consider in that geometric packing argument they mention later.
The paper's improvements: Tom: The main improvement here, according to the paper, is moving from XP algorithms parameterized by VC dimension or chromatic number to a true fixed parameter tractable algorithm for any non-trivial hereditary class of tournaments.
Jane: That means we’re getting an FPT test instead of just something that runs in time like n times some polynomial in the parameter. That’s a big jump for practical use on larger inputs.
Lu: And they also state that this result gives the very first FPT isomorphism test for tournaments when parameterized by VC dimension and chromatic number, which was previously only available as an XP algorithm, which is what we had before.
Meng: So the paper isn't just improving the complexity class; it’s providing a better complexity class for these specific parameters. It’s moving from something like time n to something like two to the power of k squared times n.
Tom: Right. And they also highlight that this method is a general technique, not just specific to tournaments, because it applies whenever you have an F-free class defined by some forbidden structure F.
Conclusion: Tom: So to wrap up the paper "FPT Isomorphism Test for F-Free Tournaments," they show that we can solve tournament isomorphism in fixed parameter time parameterized by the size of the forbidden set F.
Jane: The implication is that any tournament you define by forbidding a set of induced subtournaments F has this polynomial time isomorphism test, which is much stronger than what was known for classes like bounded twin-width.
Lu: The paper achieves this through that novel combination of spectral, geometric, combinatorial, and group-theoretic tools to discover the near bounded degree subgraph and then using group theory to solve the isomorphism.
Meng: From a deployment standpoint, running in two to the power of k squared times n times a constant factor is much better than what we were dealing with before when we had XP algorithms parameterized by VC dimension or chromatic number.
Lalam: I’m confident in this result because it connects these structural properties—the spectral bound on the eigenspace and the combinatorial coloring—to a concrete group-theoretic computation for isomorphism.
Tom: It’s definitely solid work, showing how these different mathematical fields can be combined to tackle problems that seem hard otherwise. We'll keep an eye on how this applies to other hereditary graph classes next.
TU Dresden
cs.DS, cs.DM
Submitted: 2026-09-21
Updated: 2026-11-18
Comments: 18 pages; second version adds missing attribution of earlier results and improves the write-up
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 82/100
The gist: FPT Isomorphism Test for F-Free Tournaments shows that isomorphism of F-free tournaments can be solved in FPT time f(k)·nO(1), where k denotes the size of F…
Key concepts
- FPT Isomorphism Test
- This means an algorithm that solves the problem of determining if two given tournaments are identical in time that is exponential only in a specific parameter (k, the size of F), multiplied by a polynomial factor (n). This makes solving isomorphism much faster when the forbidden structure set F is small.
- Near-bounded Degree Structure
- This is a specific subgraph found within an F-free tournament. It means that after some preprocessing using combinatorial tools, there exists a connected part of the graph where every vertex has a degree close to some bounded value, which simplifies the subsequent isomorphism check.
- 2-Dimensional Weisfeiler-Leman (2-WL) Algorithm
- This is a refinement of the standard Weisfeiler-Leman algorithm used here. It colors pairs of vertices based on their neighborhood structure in a way that is invariant under isomorphism. Using this method helps identify structural properties without relying on complex numerical computations, which keeps the algorithm within FPT time bounds.
Terminology
Summary
FPT Isomorphism Test for F-Free Tournaments shows that isomorphism of F-free tournaments can be solved in FPT time f(k)·nO(1), where k denotes the size of F, and n denotes the size of the input tournaments<ref:2609. p. 0 FPT Isomorphism Test for F-Free Tournaments
Daniel Neuen
TU Dresden
Dresden, Germany
Abstract
We show that isomorphism of F-free tournaments can be solved in FPT time f(k)·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]. 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.Where the paper says it
Where the paper says it
Generalization of Existing Results
The main contribution is generalizing prior results on specific graph parameters to all non-trivial hereditary classes of tournaments<ref:2609.24804#pg2>. Specifically, Theorem 1. p. 0 An important fact that
makes TI more accessible than GI is that every tournament has a solvable automorphism group. This follows from the fact that the automorphism group of every tournament has odd order
and the famous Feit-Thompson Theorem [8] stating that all groups of odd order are solvable. More precisely, for a
tournaments F and T, we say that T is F-free if T has no induced subtournament isomorphic
to F. The isomorphism problem for F-free tournaments can be solved in time 2
2
O(k
2)
·
n
O(1) where k := |V (F)|. FPT Isomorphism Test for F-Free Tournaments
Daniel Neuen
TU Dresden
Dresden, Germany
Abstract
We show that isomorphism of F-free tournaments can be solved in FPT time f(k)·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]. In fact, if GI cannot be solved in polynomial time, then
there are even subgraph-closed (and hence, hereditary) classes of graphs on which GI has intermediate complexity [21]. In contrast, for tournaments, our result shows that every non-trivial
hereditary class admits a polynomial-time isomorphism test.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The Core Algorithmic Strategy
The algorithm builds on a combination of spectral, geometric, combinatorial and group-theoretic tools<ref:2609.24804#pg2>. The basic strategy involves two phases after an initial step restricting to 2-WL-homogeneous tournaments<ref:2609. p. 1 The starting point for the algorithm is the FPT isomorphism
test for tournaments of bounded twin-width from [12]. The basic strategy of this algorithm
is to proceed in roughly two phases (after some initial step that restricts to so-called 2-WLhomogeneous tournaments; we ignore this step in the following overview).Where the paper says it
-
First, combinatorial methods are used to identify an isomorphism-invariant subset of edges that defines a connected spanning graph of “near-bounded degree”<ref:2609. p. 1
24804#pg4>. This is achieved by using the 2-dimensional Weisfeiler-Leman algorithm to color pairs of vertices in an isomorphism-invariant manner and proving the existence of a subset of 2-WL colors C that defines such a subgraph<ref:2609. p. 1Where the paper says it
The basic strategy of this algorithm is to proceed in roughly two phases (after some initial step that restricts to so-called 2-WLhomogeneous tournaments; we ignore this step in the following overview). First, the algorithm uses combinatorial methods to identity an isomorphism-invariant subset of the edges that defines a connected spanning graph of “near-bounded degree”.
24804#pg4>.Where the paper says it
, [17, 18] for background), which colors pairs of vertices in an isomorphism-invariant manner. Now, the key step is to prove the existence of a subset of 2-WL colors C such that taking all edges with a color from C defines a subgraph of “near-bounded degree”.
-
The second phase solves isomorphism using group-theoretic methods, extending algorithms from [1]<ref:2609. p. 1
24804#pg4>. This phase exploits the discovered “near-bounded-degree” structure to design an FPT isomorphism test<ref:2609. p. 5Where the paper says it
First, the algorithm uses combinatorial methods to identity an isomorphism-invariant subset of the edges that defines a connected spanning graph of “near-bounded degree”. Giving those edges a special color, the second phase then solves isomorphism using group-theoretic methods which extend the algorithm from [1].
24804#pg4>.Where the paper says it
Then, in the second phase, we use group-theoretic methods to solve isomorphism by exploiting the discovered “near-boundeddegree” structure. In fact, the second phase of the algorithm is essentially identical to [12] where the same “near-bounded-degree” structure is exploited to design an FPT isomorphism for 6
Bounding Structural Parameters
The proof of Theorem 3.1 relies on bounding the dimension of the eigenspace for the largest eigenvalue of a matrix associated with T<ref:2609. p. 6 1 Bounding the Multiplicity of the Largest Eigenvalue
As the first step towards proving Theorem 3. 1, we bound the dimension of the eigenspace for
the largest eigenvalue of the matrix MT defined below. First, for
an F-free tournament T, we consider the matrix
M := (A − A
T
)(A
T − A)
where A is the adjacency matrix of T, and AT denotes the transpose. This matrix is symmetric
and positive semidefinite, i.Where the paper says it
Where the paper says it
The dimension of this eigenspace, denoted by d, is bounded by 2 ≤ d ≤ K(F), where K(F) is a parameter depending only on F<ref:2609. p. 1 , all eigenvalues are non-negative. We first show that the eigenspace
of the largest eigenvalue has a dimension 2 ≤ d ≤ K(F) where K(F) is some parameter that
only depends on F. In particular, hom(F, T) = 0 if and only if T is Ffree. We start by proving the following bound that is inspired by the study of quasi-random
tournaments [6, 16].Where the paper says it
Where the paper says it
Isomorphism Testing via Group Theory
The final step of the algorithm utilizes group-theoretic methods to solve isomorphism by exploiting the discovered “near-bounded-degree” structure<ref:2609.24804#pg4>. The proof shows that if two tournaments T1 and T2 are 2-WL-homogeneous, their isomorphism can be computed in time 2(O(k 2))·nO(1)<ref:2609. p. 1 In contrast, for tournaments, our result shows that every non-trivial
hereditary class admits a polynomial-time isomorphism test. The proof of Theorem 1. In particular, we obtain the following lemma. Let T be a 2-WL-homogeneous, arc-colored tournament, and let M := MT . As such, Raßmann and Schweitzer
[23] cover more general classes of tournaments, but they only obtain XP algorithms whereas for
tournaments of twin-width k, the algorithm from [12] is an FPT algorithm. 1
arXiv:2609. An important fact that
makes TI more accessible than GI is that every tournament has a solvable automorphism group. This follows from the fact that the automorphism group of every tournament has odd order
and the famous Feit-Thompson Theorem [8] stating that all groups of odd order are solvable. Also let Γ ≤ Sym(V1) be a solvable group and θ : V1 → V2 a bijection. Then IsoΓθ(G1, G2) can be computed in polynomial time.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Final Isomorphism Test
The overall FPT isomorphism test for F-free tournaments is established by Theorem 4.3<ref:2609. p. 0 As such, Raßmann and Schweitzer
[23] cover more general classes of tournaments, but they only obtain XP algorithms whereas for
tournaments of twin-width k, the algorithm from [12] is an FPT algorithm. 1
arXiv:2609. As such, Raßmann and Schweitzer
[23] cover more general classes of tournaments, but they only obtain XP algorithms whereas for
tournaments of twin-width k, the algorithm from [12] is an FPT algorithm. 1
arXiv:2609. First, the algorithm
uses combinatorial methods to identity an isomorphism-invariant subset of the edges that defines
a connected spanning graph of “near-bounded degree”. Giving those edges a special color, the
second phase then solves isomorphism using group-theoretic methods which extend the algorithm
from [1]. However, at this point, one starts to encounter certain
numerical issues since all eigenvalues, eigenvectors and projectors need to be computed to a
sufficiently large precision. To avoid such issues, we follow a strategy similar to [9] and instead
rely on the purely combinatorial 2-WL algorithm which is known to capture many spectral
invariants (see, e.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
AI Statement
The results in this work were obtained through a discussion with ChatGPT-6 Astra<ref:2609.24804#pg2>. On an initial prompt, ChatGPT-6 Astra provided an XP algorithm (parameterized by the size of F) building on Theorem 3. p. 0 FPT Isomorphism Test for F-Free Tournaments
Daniel Neuen
TU Dresden
Dresden, Germany
Abstract
We show that isomorphism of F-free tournaments can be solved in FPT time f(k)·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]. FPT Isomorphism Test for F-Free Tournaments
Daniel Neuen
TU Dresden
Dresden, Germany
Abstract
We show that isomorphism of F-free tournaments can be solved in FPT time f(k)·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]. As such, Raßmann and Schweitzer
[23] cover more general classes of tournaments, but they only obtain XP algorithms whereas for
tournaments of twin-width k, the algorithm from [12] is an FPT algorithm. 1
arXiv:2609. As such, Raßmann and Schweitzer
[23] cover more general classes of tournaments, but they only obtain XP algorithms whereas for
tournaments of twin-width k, the algorithm from [12] is an FPT algorithm. 1
arXiv:2609. As such, Raßmann and Schweitzer
[23] cover more general classes of tournaments, but they only obtain XP algorithms whereas for
tournaments of twin-width k, the algorithm from [12] is an FPT algorithm. 1
arXiv:2609. As such, Raßmann and Schweitzer
[23] cover more general classes of tournaments, but they only obtain XP algorithms whereas for
tournaments of twin-width k, the algorithm from [12] is an FPT algorithm. 1
arXiv:2609. Then, in the second phase, we
use group-theoretic methods to solve isomorphism by exploiting the discovered “near-boundeddegree” structure. In fact, the second phase of the algorithm is essentially identical to [12]
where the same “near-bounded-degree” structure is exploited to design an FPT isomorphism for
6 Then, in the second phase, we
use group-theoretic methods to solve isomorphism by exploiting the discovered “near-boundeddegree” structure. In fact, the second phase of the algorithm is essentially identical to [12]
where the same “near-bounded-degree” structure is exploited to design an FPT isomorphism for
6Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
References
[1] Vikraman Arvind, Ilia Ponomarenko, and Grigory Ryabov. Isomorphism testing of kspanning tournaments is fixed parameter tractable. p. 0 While there is an extensive literature on GI restricted to classes of graphs (see [11, 20] for
recent surveys), restrictions of TI only started to receive more attention recently. Ponomarenko
[22] proved that TI is in polynomial time for tournaments whose automorphism group contains
a regular cyclic subgroup, and more recently Arvind, Ponomarenko, and Ryabov [1] proved that
TI is in polynomial time for edge-colored tournaments where at least one edge color induces
a (strongly) connected spanning subgraph of bounded degree (even fixed-parameter tractable
when parameterized by the out-degree). As such, Raßmann and Schweitzer
[23] cover more general classes of tournaments, but they only obtain XP algorithms whereas for
tournaments of twin-width k, the algorithm from [12] is an FPT algorithm. 1
arXiv:2609.Where the paper says it
Where the paper says it
[3] László Babai and Eugene M. p. 0 1 Introduction
The tournament isomorphism problem (TI) was recognized as a particularly interesting special
case of the graph isomorphism problem (GI) early-on. Already in 1983, Babai and Luks [3] proved
that TI can be solved in quasipolynomial time n
O(log n)
; it took 33 more years for Babai [2] to
prove that the general GI can also be solved in quasipolynomial time. As such, Raßmann and Schweitzer
[23] cover more general classes of tournaments, but they only obtain XP algorithms whereas for
tournaments of twin-width k, the algorithm from [12] is an FPT algorithm. 1
arXiv:2609.Where the paper says it
Where the paper says it
[7] John D. Dixon and Brian Mortimer. Permutation Groups, volume 163 of Graduate Texts in Mathematics<ref:2609. p. 5 4 Group Theory
Next, we describe the required tools from the group-theoretic machinery. For basic background
on permutation groups and and their computational aspects, we also refer to [7, 25, 28].Where the paper says it
[8] Walter Feit and John G. p. 0 An important fact that
makes TI more accessible than GI is that every tournament has a solvable automorphism group. This follows from the fact that the automorphism group of every tournament has odd order
and the famous Feit-Thompson Theorem [8] stating that all groups of odd order are solvable. An important fact that
makes TI more accessible than GI is that every tournament has a solvable automorphism group. This follows from the fact that the automorphism group of every tournament has odd order
and the famous Feit-Thompson Theorem [8] stating that all groups of odd order are solvable. As such, Raßmann and Schweitzer
[23] cover more general classes of tournaments, but they only obtain XP algorithms whereas for
tournaments of twin-width k, the algorithm from [12] is an FPT algorithm. 1
arXiv:2609.Where the paper says it
Where the paper says it
Where the paper says it
[9] Martin Fürer. Graph isomorphism testing without numberics for graphs of bounded eigenvalue multiplicity<ref:2609. p. 1 For general (undirected) graphs, there is a wide collection of non-trivial hereditary classes (e. , bipartite graphs,
chordal graphs, 2-degenerate graphs, etc) for which the isomorphism problem is as hard as on
general graph [4] (see also, e.Where the paper says it
[10] Martin Fürer. On the power of combinatorial and spectral invariants. p. 9 However, at this point, one starts to encounter certain
numerical issues since all eigenvalues, eigenvectors and projectors need to be computed to a
sufficiently large precision. To avoid such issues, we follow a strategy similar to [9] and instead
rely on the purely combinatorial 2-WL algorithm which is known to capture many spectral
invariants (see, e. Isomorphisms between arc-colored graphs are required to preserve the coloring. 2 Linear Algebra
For our spectral arguments, we require some background in linear algebra. As such, Raßmann and Schweitzer
[23] cover more general classes of tournaments, but they only obtain XP algorithms whereas for
tournaments of twin-width k, the algorithm from [12] is an FPT algorithm. 1
arXiv:2609.Where the paper says it
Where the paper says it
Where the paper says it
[15] Neil Immerman and Eric Lander. Describing graphs: A first-order approach to graph canonization. p. 9 1, we still need to
establish that certain properties associated with the eigenspace are “encoded” the 2-WL coloring. Let us remark at this point that, as an alternative approach, one could also work directly
with the required spectral invariants.Where the paper says it
[16] Subrahmanyam Kalyanasundaram and Asaf Shapira. A note on even cycles and quasirandom tournaments. p. 0 While there is an extensive literature on GI restricted to classes of graphs (see [11, 20] for
recent surveys), restrictions of TI only started to receive more attention recently. Ponomarenko
[22] proved that TI is in polynomial time for tournaments whose automorphism group contains
a regular cyclic subgroup, and more recently Arvind, Ponomarenko, and Ryabov [1] proved that
TI is in polynomial time for edge-colored tournaments where at least one edge color induces
a (strongly) connected spanning subgraph of bounded degree (even fixed-parameter tractable
when parameterized by the out-degree). 4 Group Theory
Next, we describe the required tools from the group-theoretic machinery. For basic background
on permutation groups and and their computational aspects, we also refer to [7, 25, 28].Where the paper says it
Where the paper says it
[17] Sandra Kiefer. Power and Limits of the Weisfeiler-Leman Algorithm. p. 1 However, the key difference lies in the analysis, and in particular how
to prove the existence of an isomorphism-invariant subset of the edges that defines a connected
spanning graph of “near-bounded degree”. More concretely, to identify the desired subset of
edges, both algorithms rely on a standard combinatorial graph isomorphism heuristic, the 2-
dimensional Weisfeiler-Leman algorithm (see, e. As such, Raßmann and Schweitzer
[23] cover more general classes of tournaments, but they only obtain XP algorithms whereas for
tournaments of twin-width k, the algorithm from [12] is an FPT algorithm. 1
arXiv:2609.Where the paper says it
Where the paper says it
[18] Sandra Kiefer. The Weisfeiler-Leman algorithm: an exploration of its power. p. 1 However, the key difference lies in the analysis, and in particular how
to prove the existence of an isomorphism-invariant subset of the edges that defines a connected
spanning graph of “near-bounded degree”. More concretely, to identify the desired subset of
edges, both algorithms rely on a standard combinatorial graph isomorphism heuristic, the 2-
dimensional Weisfeiler-Leman algorithm (see, e. As such, Raßmann and Schweitzer
[23] cover more general classes of tournaments, but they only obtain XP algorithms whereas for
tournaments of twin-width k, the algorithm from [12] is an FPT algorithm. 1
arXiv:2609.Where the paper says it
Where the paper says it
[19] Stefan Kratsch and Pascal Schweitzer. p. 0 FPT Isomorphism Test for F-Free Tournaments
Daniel Neuen
TU Dresden
Dresden, Germany
Abstract
We show that isomorphism of F-free tournaments can be solved in FPT time f(k)·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]. The basic strategy of this algorithm
is to proceed in roughly two phases (after some initial step that restricts to so-called 2-WLhomogeneous tournaments; we ignore this step in the following overview). First, the algorithm
uses combinatorial methods to identity an isomorphism-invariant subset of the edges that defines
a connected spanning graph of “near-bounded degree”. As such, Raßmann and Schweitzer
[23] cover more general classes of tournaments, but they only obtain XP algorithms whereas for
tournaments of twin-width k, the algorithm from [12] is an FPT algorithm. 1
arXiv:2609.Where the paper says it
Where the paper says it
Where the paper says it
[20] Daniel Neuen. p. 0 FPT Isomorphism Test for F-Free Tournaments
Daniel Neuen
TU Dresden
Dresden, Germany
Abstract
We show that isomorphism of F-free tournaments can be solved in FPT time f(k)·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]. In fact, if GI cannot be solved in polynomial time, then
there are even subgraph-closed (and hence, hereditary) classes of graphs on which GI has intermediate complexity [21]. In contrast, for tournaments, our result shows that every non-trivial
hereditary class admits a polynomial-time isomorphism test. As such, Raßmann and Schweitzer
[23] cover more general classes of tournaments, but they only obtain XP algorithms whereas for
tournaments of twin-width k, the algorithm from [12] is an FPT algorithm. 1
arXiv:2609.Where the paper says it
Where the paper says it
Where the paper says it
[23] Simon Raßmann and Pascal Schweitzer. p. 0 FPT Isomorphism Test for F-Free Tournaments
Daniel Neuen
TU Dresden
Dresden, Germany
Abstract
We show that isomorphism of F-free tournaments can be solved in FPT time f(k)·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]. FPT Isomorphism Test for F-Free Tournaments
Daniel Neuen
TU Dresden
Dresden, Germany
Abstract
We show that isomorphism of F-free tournaments can be solved in FPT time f(k)·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]. As such, Raßmann and Schweitzer
[23] cover more general classes of tournaments, but they only obtain XP algorithms whereas for
tournaments of twin-width k, the algorithm from [12] is an FPT algorithm. 1
arXiv:2609.Where the paper says it
Where the paper says it
Where the paper says it
[25] Joseph J. Rotman. An Introduction to the Theory of Groups, volume 148 of Graduate Texts in Mathematics, Springer-Verlag, New York, fourth edition, 1995<ref:2609. p. 5 4 Group Theory
Next, we describe the required tools from the group-theoretic machinery. For basic background
on permutation groups and and their computational aspects, we also refer to [7, 25, 28].Where the paper says it
[26] Pascal Schweitzer. p. 0 FPT Isomorphism Test for F-Free Tournaments
Daniel Neuen
TU Dresden
Dresden, Germany
Abstract
We show that isomorphism of F-free tournaments can be solved in FPT time f(k)·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]. But TI is not only special from a group-theoretic perspective. p. 0 However, even Babai’s powerful machinery did not help us to improve the upper bound for TI. But TI is not only special from a group-theoretic perspective.Where the paper says it
Where the paper says it
Where the paper says it
[27] Pascal Schweitzer. p. 0 FPT Isomorphism Test for F-Free Tournaments
Daniel Neuen
TU Dresden
Dresden, Germany
Abstract
We show that isomorphism of F-free tournaments can be solved in FPT time f(k)·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]. For general (undirected) graphs, there is a wide collection of non-trivial hereditary classes (e. , bipartite graphs,
chordal graphs, 2-degenerate graphs, etc) for which the isomorphism problem is as hard as on
general graph [4] (see also, e. 4 Group Theory
Next, we describe the required tools from the group-theoretic machinery. For basic background
on permutation groups and and their computational aspects, we also refer to [7, 25, 28]. As such, Raßmann and Schweitzer
[23] cover more general classes of tournaments, but they only obtain XP algorithms whereas for
tournaments of twin-width k, the algorithm from [12] is an FPT algorithm. 1
arXiv:2609.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[30] Boris Weisfeiler and Andrei Leman. p. 1 However, the key difference lies in the analysis, and in particular how
to prove the existence of an isomorphism-invariant subset of the edges that defines a connected
spanning graph of “near-bounded degree”. More concretely, to identify the desired subset of
edges, both algorithms rely on a standard combinatorial graph isomorphism heuristic, the 2-
dimensional Weisfeiler-Leman algorithm (see, e. Let G be a directed graph and let
AG ∈ {0, 1}
V (G)×V (G) denote its adjacency matrix. The coherent algebra of G is the algebra
A(G) ⊆ C
V (G)×V (G) obtained by closing the set {AG, AT
G, In, Jn} under scalar multiplication,
matrix addition, matrix multiplication, and Hadamard multiplication (i. As such, Raßmann and Schweitzer
[23] cover more general classes of tournaments, but they only obtain XP algorithms whereas for
tournaments of twin-width k, the algorithm from [12] is an FPT algorithm. 1
arXiv:2609.Where the paper says it
Where the paper says it
Where the paper says it
--- Page 1 ---
FPT Isomorphism Test for F-Free Tournaments
Daniel Neuen
TU Dresden
Dresden, Germany
Abstract
We show that isomorphism of F-free tournaments can be solved in FPT time f(k)·nO(1), where k denotes the size of F, and n denotes the size of the input tournaments<ref:2609.24804#pg2>. 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]. p. 0 FPT Isomorphism Test for F-Free Tournaments
Daniel Neuen
TU Dresden
Dresden, Germany
Abstract
We show that isomorphism of F-free tournaments can be solved in FPT time f(k)·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]. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
1 Introduction
The tournament isomorphism problem (TI) was recognized as a particularly interesting special case of the graph isomorphism problem (GI) early-on<ref:2609.24804#pg2>. Already in 1983, Babai and Luks [3] proved that TI can be solved in quasipolynomial time nO(log n)<ref:2609. p. 0 1 Introduction
The tournament isomorphism problem (TI) was recognized as a particularly interesting special
case of the graph isomorphism problem (GI) early-on. Already in 1983, Babai and Luks [3] proved
that TI can be solved in quasipolynomial time n
O(log n)
; it took 33 more years for Babai [2] to
prove that the general GI can also be solved in quasipolynomial time. 1 Introduction
The tournament isomorphism problem (TI) was recognized as a particularly interesting special
case of the graph isomorphism problem (GI) early-on. Already in 1983, Babai and Luks [3] proved
that TI can be solved in quasipolynomial time n
O(log n)
; it took 33 more years for Babai [2] to
prove that the general GI can also be solved in quasipolynomial time. Already in 1983, Babai and Luks [3] proved
that TI can be solved in quasipolynomial time n
O(log n)
; it took 33 more years for Babai [2] to
prove that the general GI can also be solved in quasipolynomial time. An important fact that
makes TI more accessible than GI is that every tournament has a solvable automorphism group. An important fact that
makes TI more accessible than GI is that every tournament has a solvable automorphism group. This follows from the fact that the automorphism group of every tournament has odd order
and the famous Feit-Thompson Theorem [8] stating that all groups of odd order are solvable. This follows from the fact that the automorphism group of every tournament has odd order
and the famous Feit-Thompson Theorem [8] stating that all groups of odd order are solvable. However, even Babai’s powerful machinery did not help us to improve the upper bound for TI. But TI is not only special from a group-theoretic perspective. Another remarkable result, due
to Schweitzer [26], states that TI reduces (under randomized polynomial-time reductions) to the
problem of deciding whether a tournament has a nontrivial automorphism; the so-called rigidity
problem.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
While there is an extensive literature on GI restricted to classes of graphs (see [11, 20] for recent surveys), restrictions of TI only started to receive more attention recently<ref:2609. p. 0 It is an open question whether the same holds for general graphs. While there is an extensive literature on GI restricted to classes of graphs (see [11, 20] for
recent surveys), restrictions of TI only started to receive more attention recently. While there is an extensive literature on GI restricted to classes of graphs (see [11, 20] for
recent surveys), restrictions of TI only started to receive more attention recently. Ponomarenko
[22] proved that TI is in polynomial time for tournaments whose automorphism group contains
a regular cyclic subgroup, and more recently Arvind, Ponomarenko, and Ryabov [1] proved that
TI is in polynomial time for edge-colored tournaments where at least one edge color induces
a (strongly) connected spanning subgraph of bounded degree (even fixed-parameter tractable
when parameterized by the out-degree). Ponomarenko
[22] proved that TI is in polynomial time for tournaments whose automorphism group contains
a regular cyclic subgroup, and more recently Arvind, Ponomarenko, and Ryabov [1] proved that
TI is in polynomial time for edge-colored tournaments where at least one edge color induces
a (strongly) connected spanning subgraph of bounded degree (even fixed-parameter tractable
when parameterized by the out-degree). While both of these results are very interesting from a
technical perspective, they consider fairly specialized classes of tournaments that would hardly be
called natural from a graph-theoretic point of view. While both of these results are very interesting from a
technical perspective, they consider fairly specialized classes of tournaments that would hardly be
called natural from a graph-theoretic point of view. Looking at natural graph parameters, Grohe
and the present author [12] proved that TI can be solved in time k
O(log k)n
O(1) for tournaments
of twin-width at most k. Looking at natural graph parameters, Grohe
and the present author [12] proved that TI can be solved in time k
O(log k)n
O(1) for tournaments
of twin-width at most k. Also, Raßmann and Schweitzer [23] proved that TI for tournaments
of VC dimension at most d can be solved in time n
O(d log d)
, and TI for k-colorable tournaments
can be solved in time n
O(k)
.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
How the training signal is built
All three of these parameters p (twin-width, VC dimension, chromatic number) have in common that they are hereditary<ref:2609.24804#pg2>. As the main result of this work, we generalize those results and obtain an FPT isomorphism for all non-trivial hereditary classes of tournaments<ref:2609. p. 1 , for an induced subtournament S of a tournament T, we
have that p(S) ≤ p(T). As the main result of this work, we generalize those results and obtain
an FPT isomorphism for all non-trivial hereditary classes of tournaments. 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. tournaments of twin-width at most k. Hence, the main technical contribution of this paper lies
in the first phase which discovers the “near-bounded-degree” structure.Where the paper says it
Where the paper says it
Where the paper says it
Where the gains come from
The main gain comes from proving that for an F-free tournament T, there is a cross-Q color c such that Q in Q ∃w in Q: χ 2,T (v, w) = c ≤ D(F)<ref:2609.24804#pg4>. This bound D(F) = 3K(F) − 1 is crucial for the geometric packing argument<ref:2609. p. 6 In a first step, we
prove that the eigenspace of the largest eigenvalue of a matrix associated with T has dimension
2 ≤ d ≤ K(F). Afterwards, we use geometric packing argument in the eigenspace to bound the
number of blocks in (3). The number of such
neighbors is bounded, since every point pv lies in the eigenspace of the largest eigenvalue, which
has bounded dimension d. Indeed, since all points have pairwise distance at least δ, a simple
geometric packing argument shows that, for every v ∈ V (T), there is only a bounded number of
vertices w ∈ V (T) such that ∥pv − pw∥2 = δ. The number of such
neighbors is bounded, since every point pv lies in the eigenspace of the largest eigenvalue, which
has bounded dimension d. Indeed, since all points have pairwise distance at least δ, a simple
geometric packing argument shows that, for every v ∈ V (T), there is only a bounded number of
vertices w ∈ V (T) such that ∥pv − pw∥2 = δ.Where the paper says it
Where the paper says it
Where the paper says it
Isomorphism Computation
The second phase uses group-theoretic methods to solve isomorphism by exploiting the discovered “near-bounded-degree” structure<ref:2609.24804#pg4>. For 2-WL-homogeneous tournaments, this phase is essentially identical to the algorithm from [12]<ref:2609. p. 5 Then, in the second phase, we
use group-theoretic methods to solve isomorphism by exploiting the discovered “near-boundeddegree” structure. In fact, the second phase of the algorithm is essentially identical to [12]
where the same “near-bounded-degree” structure is exploited to design an FPT isomorphism for
6 Additionally, for the parameters VC dimension and chromatic number, our result gives the first
FPT isomorphism test for tournaments. Moreover, Theorem 1. As such, Raßmann and Schweitzer
[23] cover more general classes of tournaments, but they only obtain XP algorithms whereas for
tournaments of twin-width k, the algorithm from [12] is an FPT algorithm. 1
arXiv:2609.Where the paper says it
Where the paper says it
Where the paper says it
AI Statement
The results in this work were obtained through a discussion with ChatGPT-6 Astra<ref:2609.24804#pg2>. On an initial prompt, ChatGPT-6 Astra provided an XP algorithm (parameterized by the size of F) building on Theorem 3.5, but was unable to obtain an FPT algorithm<ref:2609.24804#pg2>. The FPT algorithm was obtained in a subsequent discussion where the main additional ideas and high-level proof structure were provided by the author<ref:2609.24804#pg2>. In particular, this included the use of the “near-boundeddegree” structure and partition hierarchy (inspired by [12]) as well as the use the 2-WL algorithm to avoid numerical computations (and accompanying bit-complexity issues) which were part of the initially proposed XP algorithm (inspired by [9])<ref:2609.24804#pg2>. Finally, I stress that the write-up does not contain any AI-generated text, and is fully written by the author (based on the results of the discussion with ChatGPT-6 Astra)<ref:2609.24804#pg2>.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Develop an FPT isomorphism test for any non-trivial hereditary class of tournaments by generalizing known results for bounded twin-width, VC dimension, and chromatic number classes to arbitrary forbidden tournament F-free sets.
-
Implement a polynomial time isomorphism test for every non-trivial hereditary class of tournaments based on the result that
every non-trivial hereditary class admits a polynomial-time isomorphism test.
-
Create an algorithm to compute the isomorphism between two tournaments T1 and T2 in time 2 to the power of k squared times n times O(1), where k is the size of F, which is an improvement over XP isomorphism tests parameterized by VC dimension or chromatic number.
-
Integrate a novel combination of spectral, geometric, combinatorial and group-theoretic tools into the main algorithm to prove the existence of a subgraph with
near-bounded degree
structure in F-free tournaments. -
Enhance the 2 dimensional Weisfeiler-Leman (2-WL) algorithm's application by using it to avoid numerical computations and bit complexity issues, which is crucial for maintaining an FPT runtime instead of relying on XP algorithms.
Abstract
We show that isomorphism of F-free tournaments can be solved in FPT time f(k) times 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 combination of spectral, geometric, combinatorial and group-theoretic tools.
Sources
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time