Limitations of algebraic approaches to graph isomorphism testing

DOI10.1007/978-3-662-47672-7_13MaRDI QIDQ3448781zbMATH OpenOpenAlexFDO

Authors Christoph Berkholz, Martin Grohe

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Abstract: We investigate the power of graph isomorphism algorithms based on algebraic reasoning techniques like Gr"obner basis computation. The idea of these algorithms is to encode two graphs into a system of equations that are satisfiable if and only if if the graphs are isomorphic, and then to (try to) decide satisfiability of the system using, for example, the Gr"obner basis algorithm. In some cases this can be done in polynomial time, in particular, if the equations admit a bounded degree refutation in an algebraic proof systems such as Nullstellensatz or polynomial calculus. We prove linear lower bounds on the polynomial calculus degree over all fields of characteristic different from 2 and also linear lower bounds for the degree of Positivstellensatz calculus derivations. We compare this approach to recently studied linear and semidefinite programming approaches to isomorphism testing, which are known to be related to the combinatorial Weisfeiler-Lehman algorithm. We exactly characterise the power of the Weisfeiler-Lehman algorithm in terms of an algebraic proof system that lies between degree-k Nullstellensatz and degree-k polynomial calculus.

Recommendations

• Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
• Graph algebras and the graph isomorphism problem
• The graph isomorphism problem and approximate categories
• Graph colouring is hard for algorithms based on Hilbert's Nullstellensatz and Gröbner bases
• Lov\'asz Meets Weisfeiler and Leman

Cites work

• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• An optimal lower bound on the number of variables for graph identification
• Complexity of Null- and Positivstellensatz proofs
• Global optimization with polynomials and the problem of moments
• Graph isomorphism and theorems of Birkhoff type
• Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs
• scientific article; zbMATH DE number 1256733 (Why is no real title available?)
• scientific article; zbMATH DE number 1114017 (Why is no real title available?)
• Linear gaps between degrees for the polynomial calculus modulo distinct primes
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• Logical hierarchies in PTIME
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• On the resolution complexity of graph non-isomorphism
• Pebble games and linear equations
• Sherali-Adams relaxations and indistinguishability in counting logics
• Sherali-Adams relaxations of graph isomorphism polytopes

Cited in

(18)

• The graph isomorphism problem and approximate categories
• Is polynomial time choiceless?
• A finite-model-theoretic view on propositional proof complexity
• Lov\'asz Meets Weisfeiler and Leman
• scientific article; zbMATH DE number 7561610 (Why is no real title available?)
• Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
• Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas
• Lasserre hierarchy for graph isomorphism and homomorphism indistinguishability
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Cutting planes width and the complexity of graph isomorphism refutations
• Compressing CFI graphs and lower bounds for the Weisfeiler-Leman refinements
• From quantifier depth to quantifier number: separating structures with k variables
• Local consistency as a reduction between constraint satisfaction problems
• Pebble games and algebraic proof systems
• Symmetries and complexity (invited talk)
• Pebble games and algebraic proof systems
• Supercritical size-width tree-like resolution trade-offs for graph isomorphism
• Symmetric proofs in the ideal proof system

This page was built for publication: Limitations of algebraic approaches to graph isomorphism testing

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