May 21, 2013: Paul Bonsma: Tight Lower and Upper Bounds for the Complexity of Canonical Color Refinement

May 21, 2013Tight Lower and Upper Bounds for the Complexity of Canonical Color Refinement
Room: Zi 5126Paul Bonsma

*Color refinement* (also known as naive vertex classification or partition refinement) is a very simple, yet extremely useful algorithm routine for graph isomorphism testing. Initially, all vertices of the graph are assigned the same color. Iteratively, two vertices that currently have the same color receive different colors if for some color c, they have a different number of neighbors of color c. This process stops if no further refinement is possible, resulting in a *stable coloring* of the graph.

The resulting stable coloring has the useful property that any automorphism of the graph maps vertices to vertices of the same color. So applying this process to the disjoint union of two graphs may quickly show that they are not isomorphic. This simple test actually works for almost all pairs of nonisomorphic graphs.

Color refinement is also used as core subroutine in many more sophisticated algorithms for testing graph isomorphism. In this case, a *canonical* stable coloring is required, where the assigned colors are independent of the chosen graph representation (vertex order, edge order, etc).

In this talk we show that a canonical stable coloring of a graph G=(V,E) can be found in time O(|E| log |V|). We also show that no faster algorithm is possible, under some modest assumptions about the type of algorithm, which captures all known color refinement algorithms.

This is joint work with Christoph Berkholz and Martin Grohe.