On the relative power of algebraic approximations of graph isomorphism

2021/03/30 by Dawar, Anuj, Vagnozzi, Danny
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2103.16294

Abstract

We compare the capabilities of two approaches to approximating graph isomorphism using linear algebraic methods: the invertible map tests (introduced by Dawar and Holm) and proof systems with algebraic rules, namely polynomial calculus, monomial calculus and Nullstellensatz calculus. In the case of fields of characteristic zero, these variants are all essentially equivalent to the the Weisfeiler-Leman algorithms. In positive characteristic we show that the invertible map method can simulate the monomial calculus and identify a potential way to extend this to the monomial calculus.

Related

• Limitations of Algebraic Approaches to Graph Isomorphism Testing
• The polynomial algorithm for graphs' isomorphism testing
• The Graph Isomorphism Problem and approximate categories
• Isomorphism of graphs-a polynomial test
• Recent Advances on the Graph Isomorphism Problem