Tight lower and upper bounds for the complexity of canonical colour refinement

Christoph Berkholz, P.S. Bonsma, Martin Grohe

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

20 Citations (Scopus)
2 Downloads (Pure)

Abstract

An assignment of colours to the vertices of a graph is stable if any two vertices of the same colour have identically coloured neighbourhoods. The goal of colour refinement is to find a stable colouring that uses a minimum number of colours. This is a widely used subroutine for graph isomorphism testing algorithms, since any automorphism needs to be colour preserving. We give an $O((m+n)\log n)$ algorithm for finding a canonical version of such a stable colouring, on graphs with $n$ vertices and $m$ edges. We show that no faster algorithm is possible, under some modest assumptions about the type of algorithm, which captures all known colour refinement algorithms.
Original languageUndefined
Title of host publicationProceedings of the 21st Annual European Symposium on Algorithms (ESA 2013)
EditorsH.L. Bodlaender, G.F. Italiano
Place of PublicationBerlin
PublisherSpringer
Pages145-156
Number of pages12
ISBN (Print)978-3-642-40449-8
DOIs
Publication statusPublished - Sep 2013

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume8125
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • partition refinement
  • colour refinement
  • EWI-23837
  • METIS-300086
  • IR-88273
  • Algorithm
  • Graph Isomorphism

Cite this