Constructing hard examples for graph isomorphism

DOI10.7155/JGAA.00492MaRDI QIDQ5377355zbMATH OpenOpenAlexWikidataFDO

Authors Anuj Dawar, Kashif Ali Khan

Publication date 24 May 2019

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

random formulasgraph isomorphism testers

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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

Describes a project that uses

Uses Software

• Traces
• nauty

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)