Dimension reduction via colour refinement

DOI10.1007/978-3-662-44777-2_42MaRDI QIDQ2921438zbMATH OpenOpenAlexFDO

Authors Martin Grohe, Kristian Kersting, Martin Mladenov, Erkal Selman

Publication date 8 October 2014

Published in Algorithms - ESA 2014 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Linear programming (90C05)

Abstract: Colour refinement is a basic algorithmic routine for graph isomorphism testing, appearing as a subroutine in almost all practical isomorphism solvers. It partitions the vertices of a graph into "colour classes" in such a way that all vertices in the same colour class have the same number of neighbours in every colour class. Tinhofer (Disc. App. Math., 1991), Ramana, Scheinerman, and Ullman (Disc. Math., 1994) and Godsil (Lin. Alg. and its App., 1997) established a tight correspondence between colour refinement and fractional isomorphisms of graphs, which are solutions to the LP relaxation of a natural ILP formulation of graph isomorphism. We introduce a version of colour refinement for matrices and extend existing quasilinear algorithms for computing the colour classes. Then we generalise the correspondence between colour refinement and fractional automorphisms and develop a theory of fractional automorphisms and isomorphisms of matrices. We apply our results to reduce the dimensions of systems of linear equations and linear programs. Specifically, we show that any given LP L can efficiently be transformed into a (potentially) smaller LP L' whose number of variables and constraints is the number of colour classes of the colour refinement algorithm, applied to a matrix associated with the LP. The transformation is such that we can easily (by a linear mapping) map both feasible and optimal solutions back and forth between the two LPs. We demonstrate empirically that colour refinement can indeed greatly reduce the cost of solving linear programs.

Recommendations

• Lov\'asz Meets Weisfeiler and Leman
• Graph isomorphism, color refinement, and compactness
• On the power of color refinement
• Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
• Tight lower and upper bounds for the complexity of canonical colour refinement

Cited in

(16)

• On the expressive power of linear algebra on graphs
• Characterizing and computing weight-equitable partitions of graphs
• Dimension reduction for semidefinite programs via Jordan algebras
• Graph isomorphism, color refinement, and compactness
• On Tinhofer's linear programming approach to isomorphism testing
• On the power of color refinement
• On the expressive power of linear algebra on graphs
• Relational linear programming
• Isomorphism test for digraphs with weighted edges
• On the Weisfeiler-Leman dimension of fractional packing
• The iteration number of colour refinement
• On homomorphism indistinguishability and hypertree depth
• Compressing CFI graphs and lower bounds for the Weisfeiler-Leman refinements
• Symmetry detection in mixed-integer conic programming
• Comparative design-choice analysis of color refinement algorithms beyond the worst case
• Color refinement for relational structures

This page was built for publication: Dimension reduction via colour refinement

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