A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation

Pawan Aurora () and Shashank K. Mehta ()
Additional contact information
Pawan Aurora: IISER
Shashank K. Mehta: IIT Kanpur

Journal of Combinatorial Optimization, No 0, 20 pages

Abstract: Abstract Aurora and Mehta (J Comb Optim 36(3):965–1006, 2018) show that two graphs $$G_1,G_2$$G1,G2, on n vertices each, are isomorphic if and only if the feasible region of a certain linear program, LP-GI, intersects with the Quadratic Assignment Problem (QAP)-polytope in $${\mathbb {R}}^{(n^4+n^2)/2}$$R(n4+n2)/2. The linear program LP-GI in Aurora and Mehta (J Comb Optim 36(3):965–1006, 2018) is obtained by relaxing an integer linear program whose feasible points correspond to the isomorphisms between $$G_1,G_2$$G1,G2. In this paper we take an analogous approach with the linear programs replaced with conic programs. A completely positive description of the QAP-polytope was obtained in Povh and Rendl (Discrete Optim 6(3):231–241, 2009). By adding the graph conditions to this description we get a completely positive formulation of the graph isomorphism problem. However, analogous to integer linear programs, it is NP-hard to optimize over the cone of completely positive matrices. So we relax this formulation by replacing the cone of completely positive matrices with the cone of positive semidefinite matrices. We observe that the resulting SDP is the Lovász Theta function (Lovász in IEEE Trans Inf Theory 25(1):1–7, 1979) of a graph product of $$G_1,G_2$$G1,G2 and can be efficiently computed. We provide a natural heuristic that uses the SDP to solve the graph isomorphism problem. We run our heuristic on several pairs of non-isomorphic strongly regular graphs and find the results to be encouraging. Further, by adding the non-negativity constraints to the SDP, we obtain a doubly non-negative formulation, DNN-GI. We show that if the set of optimal points in DNN-GI contains a point of rank at most 3, then the given pair of graphs must be isomorphic.

Keywords: Graph isomorphism; Quadratic assignment problem; Lovász theta function (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00598-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v::y::i::d:10.1007_s10878-020-00598-w

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00598-w

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().