Graph Isomorphism Testing and Beyond

In the first part of my talk, I will present several recent results on the parameterized complexity of GI, most notably that isomorphism for graphs excluding K_h (the complete graph on h vertices) as a topological subgraph can be solved in time n^{polylog(k)}. This result both extends Babai's algorithm as well as several existing polynomial-time algorithms for graph isomorphism on restricted classes of graphs such as graphs of bounded tree-width, bounded genus and bounded degree. The algorithm relies on a combination of group-theoretic tools, graph-theoretic insights and the combinatorial Weisfeiler-Leman (WL) algorithm that forms a key heuristic for isomorphism testing.
Besides its applications in graph isomorphism testing, the WL algorithm is also connected to various other areas of (theoretical) computer science. In the second part of the talk, I will take a closer look at WL with a focus on connections to counting homomorphisms in graphs and related problems.