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

The graph isomorphism testing problem is considered as one of the toughest problems in graph theory. It is already a member of the class of all NP-hard problems. The authors already established in [ibid. 36, No. 3, 965--1006 (2018; Zbl 1412.90087)] that the necessary and sufficient condition for two graphs $G_1$, $G_2$, on $p$ vertices to be isomorphic is that the feasible region of a certain linear program, LP-GI, intersects with the quadratic assignment problem (QAP)-polytope in \(R^{(n^4+n^2)/2}\). The linear program LP-GI was derived by relaxing an integer linear program whose feasible points correspond to the isomorphisms between $G_1$, $G_2$. In this paper, they took a similar approach by replacing the linear programs with conic programs. \textit{J. Povh} and \textit{F. Rendl} provide a fully positive explanation of the QAP-polytope in [Discrete Optim. 6, No. 3, 231--241 (2009; Zbl 1167.90597)]. With extra graph conditions to this explanation they derived a fully positive formulation of the graph isomorphism problem. But like integer linear programs, it is NP-hard to optimize over the cone of fully positive matrices. So the authors modify this formulation with the cone of positive semidefinite matrices. They observed that the outcome SDP was the Lovász theta function [\textit{L. Lovász}, IEEE Trans. Inf. Theory 25, 1--7 (1979; Zbl 0395.94021)] of a graph product of $G_1$, $G_2$ and can be efficiently determined. They provide a canonical heuristic that employs the SDP to find a solution to the graph isomorphism problem. They ran their heuristic on several pairs of non-isomorphic strongly regular graphs and found the results that are encouraging. They then added the non-negativity constraints to the SDP and obtained a doubly non-negative formulation, DNN-GI. They also established 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. The proof techniques found in this paper are new and novel and stimulates researchers in this area to produce more.