  It is well-known that the graph isomorphism problem can be posed as an
equivalent problem of determining whether an auxiliary graph structure contains
a clique of specific order. However, the algorithms that have been developed so
far for this problem are either not efficient or not exact. In this paper, we
present a new algorithm which solves this equivalent formulation via
semidefinite programming. Specifically, we show that the problem of determining
whether the auxiliary graph contains a clique of specific order can be
formulated as a semidefinite programming problem, and can thus be (almost
exactly) solved in polynomial time. Furthermore, we show that we can determine
if the graph contains such a clique by rounding the optimal solution to the
nearest integer. Our algorithm provides a significant complexity result in
graph isomorphism testing, and also represents the first use of semidefinite
programming for solving this problem.
