Constructing hard examples for graph isomorphism

DOI10.7155/JGAA.00492zbMATH Open1411.05185arXiv1809.08154OpenAlexW2892237175WikidataQ128020179 ScholiaQ128020179MaRDI QIDQ5377355FDOQ5377355

Authors: Anuj Dawar, Kashif Ali Khan 

Publication date: 24 May 2019

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Abstract: We describe a method for generating graphs that provide difficult examples for practical Graph Isomorphism testers. We first give the theoretical construction, showing that we can have a family of graphs without any non-trivial automorphisms which also have high Weisfeiler-Leman dimension. The construction is based on properties of random 3XOR-formulas. We describe how to convert such a formula into a graph which has the desired properties with high probability. We validate the method by an experimental implementation. We construct random formulas and validate them with a SAT solver to filter through suitable ones, and then convert them into graphs. Experimental results demonstrate that the resulting graphs do provide hard examples that match the hardest known benchmarks for graph isomorphism.

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

Recommendations

• Benchmark Graphs for Practical Graph Isomorphism
• Attacks on hard instances of graph isomorphism
• ScrewBox: a randomized certifying graph-non-isomorphism algorithm
• Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs
• On the Hardness of Graph Isomorphism

zbMATH Keywords

random formulasgraph isomorphism testers

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Practical graph isomorphism. II.
• Title not available (Why is that?)
• Random graphs.
• On the Hardness of Graph Isomorphism
• Random Graph Isomorphism
• An optimal lower bound on the number of variables for graph identification
• Title not available (Why is that?)
• Short proofs are narrow—resolution made simple
• The satisfiability threshold for \(k\)-XORSAT
• Affine systems of equations and counting infinitary logic
• The efficiency of resolution and Davis-Putnam procedures
• Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
• Graph isomorphism in quasipolynomial time (extended abstract)
• On finite rigid structures
• Logical hierarchies in PTIME
• The pebbling comonad in finite model theory
• On sufficient conditions for unsatisfiability of random formulas
• Hypercycles in a random hypergraph
• Benchmark Graphs for Practical Graph Isomorphism
• An exponential lower bound for individualization-refinement algorithms for graph isomorphism
• Definable Inapproximability: New Challenges for Duplicator
• Lower bounds for existential pebble games and \(k\)-consistency tests

Cited In (3)

• Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs
• Identifiability of graphs with small color classes by the Weisfeiler-Leman algorithm
• Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas

Uses Software

• nauty
• Traces

This page was built for publication: Constructing hard examples for graph isomorphism

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