3 papers
cs.DS2026
Robust Graph Isomorphism, Quadratic Assignment and VC Dimension
Anatole Dahan, Martin Grohe, Daniel Neuen +1
We present an additive -approximation algorithm for the Graph Edit Distance problem (GED) on graphs of VC dimension running in time $n^{O(d/\varepsilon^{2})}…
cs.DS2026
Isomorphism for Tournaments of Small Twin Width
Martin Grohe, Daniel Neuen
We prove that isomorphism of tournaments of twin width at most can be decided in time . This implies that the isomorphism problem for classes of tourname…
cs.DM2025
Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
Martin Grohe, Moritz Lichter, Daniel Neuen +1
The -dimensional Weisfeiler-Leman (-WL) algorithm is a simple combinatorial algorithm that was originally designed as a graph isomorphism heuristic. It naturally finds applic…