FPT Isomorphism Test for F-Free Tournaments

arXiv:2609.24804 · cs.DS, cs.DM · Submitted 2026-09-21 · Read on arXiv

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

Where the paper says it

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

24804#pg2>. This result extends previous results on bounded twin-width, VC dimension, or chromatic number for tournaments and implies that every non-trivial hereditary class of tournaments admits a polynomial-time isomorphism test<ref:2609. p. 0
Where the paper says it

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.

24804#pg2>.

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

Where the paper says it

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.

1 states that the isomorphism problem for F-free tournaments can be solved in time 2(O(k 2))·nO(1), where k:= V (F)<ref:2609. p. 1
Where the paper says it

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

24804#pg4>. This provides an FPT isomorphism test for tournaments of VC dimension and chromatic number, which previously only offered XP algorithms<ref:2609. p. 0
Where the paper says it

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

24804#pg2>. Furthermore, the result highlights that every non-trivial hereditary class admits a polynomial-time isomorphism test for tournaments, contrasting with general graphs where GI might be harder to solve<ref:2609. p. 1
Where the paper says it

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.

24804#pg2>.

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

Where the paper says it

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

24804#pg4>.

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

    Where 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>. 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. 1
    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”.

    24804#pg4>.

  2. The second phase solves isomorphism using group-theoretic methods, extending algorithms from [1]<ref:2609. p. 1

    Where 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>. This phase exploits the discovered “near-bounded-degree” structure to design an FPT isomorphism test<ref:2609. p. 5
    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

    24804#pg4>.

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

Where the paper says it

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.

24804#pg8>. The matrix M is defined as MT:= ST · S T = -S 2/T which is symmetric and positive semidefinite<ref:2609. p. 1
Where the paper says it

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.

24804#pg8>.

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

Where the paper says it

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

24804#pg2>. This bound is derived from the fact that if T is F-free, hom(F, T) = 0, which implies a lower bound on B squared<ref:2609. p. 7
Where the paper says it

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

24804#pg9>.

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

Where the paper says it

In contrast, for tournaments, our result shows that every non-trivial hereditary class admits a polynomial-time isomorphism test. The proof of Theorem 1.

24804#pg2>. This is achieved by defining an arc-coloring via χ 2,Tj and applying Lemma 4. p. 9
Where the paper says it

In particular, we obtain the following lemma. Let T be a 2-WL-homogeneous, arc-colored tournament, and let M := MT .

1<ref:2609. p. 0
Where the paper says it

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.

24804#pg2>. By leveraging Theorem 2. p. 0
Where the paper says it

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.

7, the isomorphism set IsoΓθ(G1, G2) can be computed in polynomial time when Γ is a solvable group<ref:2609. p. 5
Where the paper says it

Also let Γ ≤ Sym(V1) be a solvable group and θ : V1 → V2 a bijection. Then IsoΓθ(G1, G2) can be computed in polynomial time.

24804#pg2>.

Final Isomorphism Test

The overall FPT isomorphism test for F-free tournaments is established by Theorem 4.3<ref:2609. p. 0

Where the paper says it

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.

24804#pg2>. This algorithm runs in time 2(O(k 2))·nO(1), where n:= max(V (T1), V (T2))<ref:2609. p. 0
Where the paper says it

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.

24804#pg2>. It involves running 2-WL on T1 and T2, and then using the results from Lemma 4. p. 1
Where 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].

2 to compute the isomorphism set Iso(Tb1[Q], Tbj'[Q']) iteratively<ref:2609.24804#pg4>. This process successfully avoids numerical computations by relying on combinatorial 2-WL coloring<ref:2609. p. 9
Where the paper says it

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.

24804#pg2>.

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

Where the paper says it

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

p. 0
Where the paper says it

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

5, but was unable to obtain an FPT algorithm<ref:2609. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

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. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

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. p. 5
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

p. 5
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

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

References

[1] Vikraman Arvind, Ilia Ponomarenko, and Grigory Ryabov. Isomorphism testing of kspanning tournaments is fixed parameter tractable. p. 0

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

Art Discret. Appl. Math., 8(2):2, 2025<ref:2609. p. 0
Where the paper says it

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.

24804#pg2>.

[3] László Babai and Eugene M. p. 0

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

Luks. Canonical labeling of graphs<ref:2609. p. 0
Where the paper says it

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.

24804#pg2>.

[7] John D. Dixon and Brian Mortimer. Permutation Groups, volume 163 of Graduate Texts in Mathematics<ref:2609. p. 5

Where the paper says it

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

24804#pg2>.

[8] Walter Feit and John G. p. 0

Where the paper says it

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.

Thompson. Solvability of groups of odd order. p. 0
Where the paper says it

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.

Pacific J. Math., 13:775–1029, 1963<ref:2609. p. 0
Where the paper says it

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.

24804#pg7>.

[9] Martin Fürer. Graph isomorphism testing without numberics for graphs of bounded eigenvalue multiplicity<ref:2609. p. 1

Where the paper says it

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.

24804#pg2>.

[10] Martin Fürer. On the power of combinatorial and spectral invariants. p. 9

Where the paper says it

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.

Linear Algebra Appl. p. 2
Where the paper says it

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.

, 432(9):2373–2380, 2010<ref:2609. p. 0
Where the paper says it

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.

24804#pg2>.

[15] Neil Immerman and Eric Lander. Describing graphs: A first-order approach to graph canonization. p. 9

Where the paper says it

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.

In Alan L. Selman, editor, Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988, pages 59–81<ref:2609.24804#pg6>.

[16] Subrahmanyam Kalyanasundaram and Asaf Shapira. A note on even cycles and quasirandom tournaments. p. 0

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

J. Graph Theory, 73(3):260–266, 2013<ref:2609. p. 5
Where the paper says it

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

24804#pg2>.

[17] Sandra Kiefer. Power and Limits of the Weisfeiler-Leman Algorithm. p. 1

Where the paper says it

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.

PhD thesis, RWTH Aachen University, 2020<ref:2609. p. 0
Where the paper says it

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.

24804#pg6>.

[18] Sandra Kiefer. The Weisfeiler-Leman algorithm: an exploration of its power. p. 1

Where the paper says it

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.

ACM SIGLOG News, 7(3):5–27, 2020<ref:2609. p. 0
Where the paper says it

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.

24804#pg6>.

[19] Stefan Kratsch and Pascal Schweitzer. p. 0

Where the paper says it

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

Graph isomorphism for graph classes characterized by two forbidden induced subgraphs. p. 1
Where 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”.

Discret. Appl. Math., 216:240–253, 2017<ref:2609. p. 0
Where the paper says it

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.

24804#pg2>.

[20] Daniel Neuen. p. 0

Where the paper says it

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

Parameterized complexity of graph isomorphism testing. p. 1
Where the paper says it

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.

Comput. Sci. Rev., 60:100918, 2026<ref:2609. p. 0
Where the paper says it

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.

24804#pg2>.

[23] Simon Raßmann and Pascal Schweitzer. p. 0

Where the paper says it

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

Isomorphism of tournaments with bounded VC dimension. p. 0
Where the paper says it

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

CoRR, abs/2608.14486, 2026<ref:2609. p. 0
Where the paper says it

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.

24804#pg2>.

[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

Where the paper says it

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

24804#pg2>.

[26] Pascal Schweitzer. p. 0

Where the paper says it

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

A polynomial-time randomized reduction from tournament isomorphism to tournament asymmetry. p. 0
Where the paper says it

But TI is not only special from a group-theoretic perspective. p. 0

Where the paper says it

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.

In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017<ref:2609.24804#pg2>.

[27] Pascal Schweitzer. p. 0

Where the paper says it

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

Towards an isomorphism dichotomy for hereditary graph classes. p. 1
Where the paper says it

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.

Theory Comput. p. 5
Where the paper says it

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

Syst., 61(4):1084–1127, 2017<ref:2609. p. 0
Where the paper says it

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.

24804#pg6>.

[30] Boris Weisfeiler and Andrei Leman. p. 1

Where the paper says it

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.

The reduction of a graph to canonical form and the algebra which appears therein. p. 4
Where the paper says it

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.

NTI, Series 2, 1968<ref:2609. p. 0
Where the paper says it

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.

24804#pg6>.

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

Where the paper says it

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

It also implies that every non-trivial hereditary class of tournaments admits a polynomial-time isomorphism test<ref:2609. p. 0
Where the paper says it

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.

24804#pg2>. Our algorithm builds on a novel combination of spectral, geometric, combinatorial and group-theoretic tools<ref:2609. p. 0
Where the paper says it

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.

24804#pg2>.

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

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

24804#pg2>. It took 33 more years for Babai [2] to prove that the general GI can also be solved in quasipolynomial time<ref:2609. p. 0
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. 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.

24804#pg2>. An important fact that makes TI more accessible than GI is that every tournament has a solvable automorphism group<ref:2609. p. 0
Where the paper says it

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.

24804#pg2>. 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<ref:2609. p. 0
Where the paper says it

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.

24804#pg2>. However, even Babai’s powerful machinery did not help us to improve the upper bound for TI<ref:2609. p. 0
Where the paper says it

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.

24804#pg2>. 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<ref:2609. p. 0
Where the paper says it

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.

24804#pg2>.

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

Where the paper says it

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.

24804#pg2>. 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)<ref:2609. p. 0
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. 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).

24804#pg2>. 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<ref:2609. p. 0
Where the paper says it

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.

24804#pg2>. Looking at natural graph parameters, Grohe and the present author [12] proved that TI can be solved in time kO(log k)nO(1) for tournaments of twin-width at most k<ref:2609. p. 0
Where the paper says it

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.

24804#pg2>. Also, Raßmann and Schweitzer [23] proved that TI for tournaments of VC dimension at most d can be solved in time nO(d log d)<ref:2609. p. 0
Where the paper says it

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

24804#pg2>.

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

Where the paper says it

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

24804#pg2>. The proof relies on a novel combination of spectral, geometric, combinatorial and group-theoretic tools<ref:2609. p. 0
Where the paper says it

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.

24804#pg2>. The key technical contribution lies in the first phase which discovers the “near-bounded-degree” structure<ref:2609. p. 6
Where the paper says it

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.

24804#pg4>.

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

Where the paper says it

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

24804#pg8>. The spectral analysis shows that the eigenspace of the largest eigenvalue of M has a dimension d ≤ K(F)<ref:2609. p. 2
Where the paper says it

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 = δ.

24804#pg2>. This small dimension is essential for bounding the number of points in geometric packing arguments<ref:2609. p. 2
Where the paper says it

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 = δ.

24804#pg2>.

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

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

24804#pg4>. The final result, Theorem 4. p. 1
Where the paper says it

Additionally, for the parameters VC dimension and chromatic number, our result gives the first FPT isomorphism test for tournaments. Moreover, Theorem 1.

3, provides a general FPT isomorphism test for any pair of tournaments T1 and T2 in time 2(O(k 2))·nO(1)<ref:2609. p. 0
Where the paper says it

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.

24804#pg2>.

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

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

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

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

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

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