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

DOI10.1007/S00224-016-9686-0MaRDI QIDQ2398207zbMATH OpenOpenAlexWikidataFDO

Authors Christoph Berkholz, Paul Bonsma, Martin Grohe

Publication date 15 August 2017

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1509.08251

zbMATH Keywords

canonical labellingcolour refinementgraph isomorphismpartition refinement

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

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)logn)$ 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.

Recommendations

• Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
• Tight lower bounds for the complexity of multicoloring
• Tight lower bounds for the complexity of multicoloring
• Complexity of coloring reconfiguration under recolorability constraints
• On the parameterized complexity of colorful components and related problems
• Approximation Algorithms for Bounded Color Matchings via Convex Decompositions
• Convex Recoloring Revisited: Complexity and Exact Algorithms
• On the complexity of solving or approximating convex recoloring problems

Cites work

• A linear time solution to the single function coarsest partition problem
• An optimal lower bound on the number of variables for graph identification
• Circular Sturmian words and Hopcroft's algorithm
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Elements of finite model theory.
• Engineering an efficient canonical labeling tool for large and sparse graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• Finite model theory and its applications.
• scientific article; zbMATH DE number 3823850 (Why is no real title available?)
• scientific article; zbMATH DE number 3723875 (Why is no real title available?)
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 1004939 (Why is no real title available?)
• Implementation and Application of Automata
• Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps
• Partitioning a graph in \(O(|A|\log_ 2|V|)\)
• Practical graph isomorphism. II.
• Random Graph Isomorphism
• Three Partition Refinement Algorithms

Cited in

(20)

• From generic partition refinement to weighted tree automata minimization
• Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
• Dimension reduction via colour refinement
• On the power of color refinement
• scientific article; zbMATH DE number 1004939 (Why is no real title available?)
• Quasifibrations of graphs to find symmetries and reconstruct biological networks
• Efficient and modular coalgebraic partition refinement
• Isomorphism Testing for Graphs Excluding Small Minors
• Lowerbounds for Bisimulation by Partition Refinement
• Generic partition refinement and weighted tree automata
• Canonization of a random circulant graph by counting walks
• Explicit Hopcroft's trick in categorical partition refinement
• Hypergraph isomorphism for groups with restricted composition factors
• Satsuma: structure-based symmetry breaking in SAT
• Computing minimal distinguishing Hennessy-Milner formulas is NP-hard, but variants are tractable
• Isomorphism testing for graphs excluding small topological subgraphs
• An algorithmic meta theorem for homomorphism indistinguishability
• Comparative design-choice analysis of color refinement algorithms beyond the worst case
• Canonical labeling of sparse random graphs
• Color refinement for relational structures

Describes a project that uses

Uses Software

• bliss
• nauty
• Traces

This page was built for publication: Tight lower and upper bounds for the complexity of canonical colour refinement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2398207)