Completely Positive formulation of the Graph Isomorphism Problem

Given two graphs $G_1$ and $G_2$ on $n$ vertices each, we define a graph $G$ on vertex set $V_1times V_2$ and the edge set as the union of edges of $G_1times bar{G_2}$, $bar{G_1}times G_2$, ${(v,u),(v,u))(|u,uin V_2}$ for each $vin V_1$, and ${((u,v),(u,v))|u,uin V_1}$ for each $vin V_2$. We consider the completely-positive Lovasz $vartheta$ function, i.e., $cpvartheta$ function for $G$. We show that the function evaluates to $n$ whenever $G_1$ and $G_2$ are isomorphic and to less than $n-1/(4n^4)$ when non-isomorphic. Hence this function provides a test for graph isomorphism. We also provide some geometric insight into the feasible region of the completely positive program.