Current Challenges in Isomorphism Testing and Graph Canonization
Final Report Abstract
The computational complexity of the graph isomorphism and canonization problems is one of the most significant open questions in theoretical computer science. Babai’s isomorphism algorithm (2016), a major achievement in this field, raises the challenging question of whether a superpolynomial running time is intrinsic to isomorphism testing or merely a result of the limitations of currently available methods. This project primarily focuses on combinatorial refinement techniques, which are a basic ingredient of Babai’s approach. Our overarching goal is to identify, as precisely as possible, the “part” of the problem tractable by these techniques. It is well known that a relatively simple combinatorial refinement method is an efficient tool for the canonization of almost all graphs. Specifically, if a graph is chosen at random, this method with high probability produces a canonical isomorphic copy of the graph. The success of combinatorial refinement in the average case relies heavily on the fact that a random graph is very likely to be asymmetric. We demonstrate that combinatorial refinement can also be effective for graphs with symmetries (i.e., those admitting nontrivial automorphisms). Our analysis encompasses two distinct cases: sparse random graphs in the evolutional Erdős-Rényi model and vertex-transitive graphs. Another objective of our research is to obtain an efficiently checkable characterization of graphs that are “easy instances” for a specified isomorphism-testing approach. We address this problem for the 2-dimensional Weisfeiler-Leman (WL) algorithm in the context of graphs with small color multiplicity. This case is particularly interesting because it includes the famous Cai-Fürer-Immerman graphs, which present a significant challenge to the WL algorithm at any dimension. A substantial portion of our work is devoted to WL-invariant graph parameters, which are parameters that remain equal for any two graphs indistinguishable by the WL algorithm. The results obtained in this direction are relevant to several other areas, including the design of graph neural networks, chemical graph theory, the analysis of LP-relaxations of NP-hard optimization problems, and combinatorics.
Link to the final report
https://doi.org/10.18452/33141
Publications
-
Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism. ACM Transactions on Computational Logic, 20(2), 1-18.
Verbitsky, Oleg & Zhukovskii, Maksim
-
On Weisfeiler-Leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sciences, 113, 42-59.
Arvind, V.; Fuhlbrück, Frank; Köbler, Johannes & Verbitsky, Oleg
-
Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm. SIAM Journal on Discrete Mathematics, 35(3), 1792-1853.
Fuhlbrück, Frank; Köbler, Johannes & Verbitsky, Oleg
-
Local WL invariance and hidden shades of regularity. Discrete Applied Mathematics, 305, 191-198.
Fuhlbrück, Frank; Köbler, Johannes & Verbitsky, Oleg
-
The Weisfeiler-Leman algorithm and recognition of graph properties. Theoretical Computer Science, 895, 96-114.
Fuhlbrück, Frank; Köbler, Johannes; Ponomarenko, Ilia & Verbitsky, Oleg
-
On Anti-stochastic Properties of Unlabeled Graphs. Lecture Notes in Computer Science, 300-312. Springer International Publishing.
Kiselev, Sergei; Kupavskii, Andrey; Verbitsky, Oleg & Zhukovskii, Maksim
-
On the Weisfeiler-Leman dimension of fractional packing. Information and Computation, 288, 104803.
Arvind, V.; Fuhlbrück, Frank; Köbler, Johannes & Verbitsky, Oleg
-
Canonization of a random graph by two matrix-vector multiplications. In Proc. of the 31st Ann. European Symposium on Algorithms (ESA’23), volume 274 of LIPIcs, pages 100:1–100:13.
O. Verbitsky & M. Zhukovskii
-
Canonical labeling of sparse random graphs
O. Verbitsky & M. Zhukovskii
-
Canonization of a Random Circulant Graph by Counting Walks. Lecture Notes in Computer Science, 319-334. Springer Nature Singapore.
Verbitsky, Oleg & Zhukovskii, Maksim
-
Combinatorial refinement on circulant graphs. computational complexity, 33(2).
Kluge, Laurence
-
Gathering information about a graph by counting walks from a single vertex
F. Fuhlbrück, J. Köbler, O. Verbitsky & M. Zhukovskii
-
On a hierarchy of spectral invariants for graphs. In Proc. of the 41st Int. Symposium on Theoretical Aspects of Computer Science, (STACS’24), volume 289 of LIPIcs, pages 6:1–6:18
V. Arvind, F. Fuhlbrück, J. Köbler & O. Verbitsky
-
New Bounds for the Optimal Density of Covering Single-Insertion Codes via the Turán Density. IEEE Transactions on Information Theory, 71(6), 4260-4266.
Pikhurko, Oleg; Verbitsky, Oleg & Zhukovskii, Maksim
-
On the expressibility of the reconstructional color refinement. Theoretical Computer Science, 1047, 115321.
Arvind, V.; Köbler, Johannes & Verbitsky, Oleg
