The QAP-polytope and the graph isomorphism problem

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

Journal of Combinatorial Optimization, 2018, vol. 36, issue 3, No 15, 965-1006

Abstract: Abstract In this paper we propose a geometric approach to solve the Graph Isomorphism (GI in short) problem. Given two graphs $$G_1, G_2$$ G 1 , G 2 , the GI problem is to decide if the given graphs are isomorphic i.e., there exists an edge preserving bijection between the vertices of the two graphs. We propose an Integer Linear Program (ILP) that has a non-empty solution if and only if the given graphs are isomorphic. The convex hull of all possible solutions of the ILP has been studied in literature as the Quadratic Assignment Problem (QAP) polytope. We study the feasible region of the linear programming relaxation of the ILP and show that the given graphs are isomorphic if and only if this region intersects with the QAP-polytope. As a consequence, if the graphs are not isomorphic, the feasible region must lie entirely outside the QAP-polytope. We study the facial structure of the QAP-polytope with the intention of using the facet defining inequalities to eliminate the feasible region outside the polytope. We determine two new families of facet defining inequalities of the QAP-polytope and show that all the known facet defining inequalities are special instances of a general inequality. Further we define a partial ordering on each exponential sized family of facet defining inequalities and show that if there exists a common minimal violated inequality for all points in the feasible region outside the QAP-polytope, then we can solve the GI problem in polynomial time. We also study the general case when there are k such inequalities and give an algorithm for the GI problem that runs in time exponential in k.

Keywords: Quadratic assignment problem; Graph isomorphism problem; Polyhedral combinatorics (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0266-x 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:36:y:2018:i:3:d:10.1007_s10878-018-0266-x

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

DOI: 10.1007/s10878-018-0266-x

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 ().