A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation
- PDF / 380,513 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 4 Downloads / 173 Views
A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation Pawan Aurora1
· Shashank K. Mehta 2
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Aurora and Mehta (J Comb Optim 36(3):965–1006, 2018) show that two graphs G 1 , G 2 , 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 4 2 (QAP)-polytope in R(n +n )/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 . 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 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.
B
Pawan Aurora [email protected] Shashank K. Mehta [email protected]
1
IISER, Bhopal, India
2
IIT Kanpur, Kanpur, India
123
Journal of Combinatorial Optimization
Keywords Graph isomorphism · Quadratic assignment problem · Lovász theta function
1 Introduction The graph isomorphism problem (GI) is a well-studied computational problem; listed as an open problem in Karp (1972). Formally, given two graphs G 1 and G 2 on n vertices each, GI is a decision problem that asks if there exists a bijection σ : V (G 1 ) → V (G 2 ) such that {u, v} ∈ E(G 1 ) iff {σ (u), σ (v)} ∈ E(G 2 ). Each such bijection is called an isomorphism between G 1 , G 2 . Without loss of generality, we assume that the vertices in both the graphs are labeled by integers 1, . . . , n. Hence V (G 1 ) = V (G 2 ) = [n] and each bijection is a permutation of 1, . . . , n. The most successful approach in tackling the GI problem has been a group-theoretic approach. The fastest known algorithm for GI for general graphs uses this approach and runs in quasipolynomial time (Babai 2016). A polyhedral approach, like the one used in Aurora
Data Loading...
