
We present an isomorphism test for graphs of Euler genus g running in time 2^{O(g^4 log g)}n^{O(1)}. Our algorithm provides the first explicit upper bound on the dependence on g for an fpt isomorphism test parameterized by the Euler genus of the input graphs. The only previous fpt algorithm runs in time f(g)n for some function f (Kawarabayashi 2015). Actually, our algorithm even works when the input graphs only exclude K_{3,h} as a minor. For such graphs, no fpt isomorphism test was known before. The algorithm builds on an elegant combination of simple group-theoretic, combinatorial, and graph-theoretic approaches. In particular, we introduce (t,k)-WL-bounded graphs which provide a powerful tool to combine group-theoretic techniques with the standard Weisfeiler-Leman algorithm. This concept may be of independent interest.
graph isomorphism, Weisfeiler-Leman algorithm, FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Analysis of algorithms and problem complexity, Mathematics of computing → Graphs and surfaces, 004, Theory of computation → Fixed parameter tractability, Theory of computation → Graph algorithms analysis, Euler genus, Graph theory (including graph drawing) in computer science, fixed-parameter tractability, Computer Science - Data Structures and Algorithms, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), Nonnumerical algorithms, Computer Science - Discrete Mathematics, ddc: ddc:004
graph isomorphism, Weisfeiler-Leman algorithm, FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Analysis of algorithms and problem complexity, Mathematics of computing → Graphs and surfaces, 004, Theory of computation → Fixed parameter tractability, Theory of computation → Graph algorithms analysis, Euler genus, Graph theory (including graph drawing) in computer science, fixed-parameter tractability, Computer Science - Data Structures and Algorithms, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), Nonnumerical algorithms, Computer Science - Discrete Mathematics, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
