Constructing Hard Examples for Graph Isomorphism

DOI10.7155/jgaa.00492zbMath1411.05185arXiv1809.08154OpenAlexW2892237175WikidataQ128020179 ScholiaQ128020179MaRDI QIDQ5377355

Kashif Ali Khan, Anuj Dawar

Publication date: 24 May 2019

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

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)

Related Items (2)

Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas ⋮ Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm

Uses Software

• nauty
• Traces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Affine systems of equations and counting infinitary logic
• An optimal lower bound on the number of variables for graph identification
• Logical hierarchies in PTIME
• Practical graph isomorphism. II.
• The Efficiency of Resolution and Davis--Putnam Procedures
• Random Graph Isomorphism
• Hypercycles in a random hypergraph
• Short proofs are narrow—resolution made simple
• On the Hardness of Graph Isomorphism
• On finite rigid structures
• Definable Inapproximability: New Challenges for Duplicator
• Benchmark Graphs for Practical Graph Isomorphism
• An exponential lower bound for individualization-refinement algorithms for graph isomorphism
• Graph isomorphism in quasipolynomial time [extended abstract]
• The Satisfiability Threshold fork-XORSAT
• On sufficient conditions for unsatisfiability of random formulas
• Lower Bounds for Existential Pebble Games and k-Consistency Tests
• Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution

This page was built for publication: Constructing Hard Examples for Graph Isomorphism