The Weisfeiler-Lehman Method and Graph Isomorphism Testing
arXiv (Cornell University)Published 27 January 2011Open access
B. L. Douglas
Citations40
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
Properties of the `$k$-equivalent' graph families constructed in Cai, Fürer and Immerman, and Evdokimov and Ponomarenko are analysed relative the the recursive $k$-dim WL method. An extension to the recursive $k$-dim WL method is presented that is shown to efficiently characterise all such types of `counterexample' graphs, under certain assumptions. These assumptions are shown to hold in all known cases.
Keywords
Computer Science
Journal of Symbolic ComputationPractical graph isomorphism, II
1,619 Citations2013Brendan D. McKay, Adolfo Piperno
The description of the best known program nauty is brought up to date and an innovative approach called Traces that outperforms the competitors for many difficult graph classes is described.
COMBINATORICAAn optimal lower bound on the number of variables for graph identification
502 Citations1992Jin‐Yi Cai, Martin F�rer +1 more
It is shown that Ω(n) variables are needed for first-order logic with counting to identify graphs onn vertices, equivalent to the (k−1)-dimensional Weisfeiler-Lehman method, and the lower bound is optimal up to multiplication by a constant.
Journal of Graph TheoryThe graph isomorphism disease
460 Citations1977Ronald C. Read, Derek G. Corneil
The present state of the art of isomorphism testing is surveyed, its relationship to NP-completeness is discussed, and some of the difficulties inherent in this particularly elusive and challenging problem are indicated.
Canonical labeling of graphs
412 Citations1983László Babai, Eugene M. Luks
An algebraic approach to the problem of assigning canonical forms to graphs by computing canonical forms and the associated canonical labelings in polynomial time is announced.
The Graph Isomorphism Problem : Its Structural Complexity
401 Citations1993Johannes Köbler, Uwe Schöning +1 more
Linear time algorithm for isomorphism of planar graphs (Preliminary Report)
339 Citations1974John E. Hopcroft, Jin Kue Wong
The time bound for planar graph isomorphism is improved to O(|V|) time and the algorithm can be easily extended to partition a set of planar graphs into equivalence classes of isomorphic graphs in time linear in the total number of vertices in all graphs in the set.
SIAM Journal on ComputingRandom Graph Isomorphism
305 Citations1980László Babai, Paul Erdo ̋s +1 more
A straightforward linear time canonical labeling algorithm is shown to apply to almost all graphs, and any graph Y can be easily tested for isomorphism to X by an extremely naive linear time algorithm.
Isomorphism of graphs with bounded eigenvalue multiplicity
161 Citations1982László Babai, D. Yu. Grigoryev +1 more
Two polynomial time algorithms are described which test isomorphism of undirected graphs whose eigenvalues have bounded multiplicity, if X and Y are graphs of eigenvalue multiplicity m.
Physical Review ATwo-particle quantum walks applied to the graph isomorphism problem
150 Citations2010John King Gamble, Mark Friesen +3 more
Isomorphism testing for graphs of bounded genus
147 Citations1980Gary L. Miller
This result is noteworthy for at least two reasons: first, it extends the polynomial time isomorphism results for the plane [HT 72] and also the projective plane [L 80] to arbitrary surfaces and secondly it gives one of the few known natural decompositions of the isomorphicism problem into an infinite hierarchy of problems.
Journal of Mathematical SciencesGraph isomorphism problem
144 Citations1985V. N. Zemlyachenko, N. M. Korneenko +1 more
Journal of Combinatorial Theory Series B6-Transitive graphs
141 Citations1980Peter J. Cameron
It is shown that a 6-transitive graph is complete multipartite, or complete bipartite with a matching deleted, or a cycle, or one of three special graphs on 9, 12 and 20 vertices.
Computational complexity and the classification of finite simple groups
124 Citations1983László Babai, William M. Kantor +1 more
It appears that unless there is another radical breakthrough in ISO, independent of the previous one, the simple groups classification is an indispensable tool for further developments.
SIAM Journal on ComputingLinear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
87 Citations1981Charles J. Colbourn, Kellogg S. Booth
An algorithm based upon Edmonds’s procedure for testing isomorphism of trees is extended to answer various questions concerning automorphisms of a labeled forest.
Isomorphism of graphs of bounded valence can be tested in polynomial time
76 Citations1980Eugene M. Luks
Testing isomorphism of graphs of valence ≤ t is polynomial-time reducible to the color automorphism problem for groups with small simple sections, and some results on primitive permutation groups are used to show that the algorithm runs inPolynomial time.
Journal of Combinatorial Theory Series BSymmetric squares of graphs
69 Citations2006Koenraad M. R. Audenaert, Chris Godsil +2 more
It is shown that the spectra of the symmetric square of strongly regular graphs with the same parameters are equal and the connection with generic exchange Hamiltonians in quantum mechanics is discussed.
Lecture notes in computer scienceGraph isomorphism is in the low hierarchy
45 Citations2006Uwe Schöning
It is shown that the graph isomorphism problem is located in the low hierarchy in NP, which implies that this problem is not NP-complete (not even under weaker forms of polynomial-time reducibilities, such as γ-reducibility) unless the polyn coefficient hierarchy collapses.
Journal of Combinatorial Theory Series BSpectra of symmetric powers of graphs and the Weisfeiler–Lehman refinements
39 Citations2010Afredo Alzaga, Rodrigo Iglesias +1 more
It is proved that if the well-known 2k-dimensional Weisfeiler-Lehman method fails to distinguish two given graphs, then their k-th powers - and theirk-th symmetric powers - are cospectral.
The Electronic Journal of CombinatoricsOn Highly Closed Cellular Algebras and Highly Closed Isomorphisms
37 Citations1998Сергей Евдокимов, Ilia Ponomarenko
It is shown that for any $m$ there exist-closed algebras on O(m) points which are not Schurian and-isomorphisms of cellular algeBRas on $O(m), which enables us to find for any £m$ an edge colored graph with $O (m) vertices satisfying the m-vertex condition and having non-Schurian adjacency algebra.
The Electronic Journal of CombinatoricsNon-Isomorphic Graphs with Cospectral Symmetric Powers
34 Citations2009A. Rahnamai Barghi, Ilya Ponomarenko
It is shown that given a positive integer $m$ there exist infinitely many pairs of non-isomorphic graphs with cospectral symmetry powers, based on theory of multidimensional extensions of coherent configurations.
Graph isomorphism, general remarks
28 Citations1977Gary L. Miller
The relative computational complexity of generalizations and restrictions of the graph isomorphism problem is analyzed and it is shown that valence seems to be important in regular undirected graphs.
WORLD SCIENTIFIC eBooksCoherent configurations, association schemes and permutation groups
26 Citations2003Peter J. Cameron
Discrete Applied MathematicsCoherent algebras and the graph isomorphism problem
17 Citations1989Shmuel Friedland
The concept of breaking up coherent algebras which embeds the given coherent algebra into a coherent algebra of a greater dimension and reduces the multiplicity of the algebra is introduced.
arXiv (Cornell University)k-Boson Quantum Walks Do Not Distinguish Arbitrary Graphs
10 Citations2010Jamie Smith