Linear Programming Heuristics for the Graph Isomorphism Problem

2016/11/02 by Reza Takapoui, Stephen Boyd, Takapoui, Reza +1 · 1 citation
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.DS #math.OC

paper · pdf · doi:10.48550/arxiv.1611.00711

arxiv created 2016/11/02 · arxiv updated 2016/11/03

Abstract

An isomorphism between two graphs is a bijection between their vertices that preserves the edges. We consider the problem of determining whether two finite undirected weighted graphs are isomorphic, and finding an isomorphism relating them if the answer is positive. In this paper we introduce effective probabilistic linear programming (LP) heuristics to solve the graph isomorphism problem. We motivate our heuristics by showing guarantees under some conditions, and present numerical experiments that show effectiveness of these heuristics in the general case.

Cited by

• Optimal graph joining with applications to isomorphism detection and identification

Related

• Graph Isomorphism: Mixed-Integer Convex Optimization from First-Order Methods
• A Simple Algorithm for a Computationally Hard Problem
• The direct algorithm for solving of the graph isomorphism problem
• Continuous optimization methods for the graph isomorphism problem
• Recent Advances on the Graph Isomorphism Problem