Tim Seppelt: The Tournament Isomorphism Problem
Contact
The Graph Isomorphism Problem (GI), i.e. the computational problem of deciding whether two given graphs X and Y admit an isomorphism X↔Y , is of both theoretical and practical relevance in Computer Science and many adjacent fields. For example, in chemistry it is desirable to determine whether two molecules encoded as graphs are structurally the same. The main interest from a theoretical viewpoint stems from the fact that despite intensive research efforts, the complexity of GI remains unknown. It is neither established that GI is NP-complete nor that it is in P. The best known algorithm, developed by Babai, runs in quasi-polynomial time in the number of vertices of the input graphs.
In order to resolve the complexity status of GI, restricted graph classes such as planar graphs and graphs with excluded minors have been considered in the past . In each of these cases, researchers succeeded in showing that GI, when restricted to these classes, can be solved in polynomial time.
While the aforementioned graph classes have been eliminated as barriers for a potential polynomial time algorithm for GI, the class of tournaments persists in representing a bottleneck. Tournaments are directed graphs whose underlying undirected graphs are complete. The best known algorithm for the Tournament Isomorphism Problem (TI) from Babai and Luks.
Faster Algorithms for TI. Although decades-long research efforts have produced a variety of tools for variants of the GI, only a few methods tailored for the TI are known. TI fundamentally differs from other variants of GI in the sense that the automorphism group of a tournament is soluble which renders an efficient treatment of the occurring groups possible. This in turn creates the need for refined combinatorial techniques. Subsequently, possible approaches for resolving the complexity status of TI are outlined.
Probabilistic Approaches. Probabilistic methods have been fruitfully used in the past in the context of TI. This includes randomized algorithms and reductions but also probabilistic arguments used to derive structural insights into the involved combinatorial objects. It is, therefore, desirable to further develop such probabilistic techniques in order to deepen the understanding of TI.
Exploiting Regularity. Whenever vertices of a graph can be distinguished, e.g. by their degrees, divide-and conquer techniques can be applied efficiently. These strategies fail if the graphs considered are regular. Looking at arcs instead of vertices gives rise to more powerful notions such as strong regularity. Especially in the realm of undirected graphs, the study of strongly regular graphs has led to a deep structural insights and advanced algorithms. This raises the question as to whether a structure theory for highly regular tournaments can be developed.
The Weisfeiler–Leman Algorithm. The Weisfeiler–Leman (WL) algorithm is a ubiquitous tool in the context of the Graph Isomorphism Problem. Its k-dimensional version colors ktuples of vertices according to their local structure. It is, hence, natural to identify levels of regularity with monochromaticity with respect to WL in certain dimensions. For example, graphs are strongly regular if and only if they are monochromatic with respect to 2-WL. Along these lines, the power of WL deserves further scrutiny.