TY - JOUR

T1 - Performance Comparison of Randomized Local Search, (1+1)-Evolutionary Algorithm and Genetic Algorithm for Graph Isomorphism Problem using Permutation Matrix Search Space

AU - Puri, Akshitha

AU - Batra, Gunveen

AU - Ajitha Shenoy, K. B.

N1 - Publisher Copyright:
© 2022, International Association of Engineers. All rights reserved.

PY - 2022/5/16

Y1 - 2022/5/16

N2 - —Graph isomorphism problem (GIP) is a class NP Problem and is a well-studied problem in graph and complexity theory. It is still an open problem, whether GIP is in class P or NP-complete. In the literature, no meta-heuristics are applied to GIP. However, few studies in the literature show that the meta-heuristic algorithms are applied to the subgraph isomorphism problem, which is a known NP-Complete problem and extension of GIP. This article proposes a new search space called permutation matrix space for GIP. Two search space elements are neighbors if one is obtained from the other by swapping any two distinct rows. The work shows that the magnification of permutation matrix space is bounded below by n/2. Magnification is one of the main structural properties of a search graph which implies the number of arcs going out from any cut-set in the search graph. The article studies the performance of Randomized Local Search (RLS), (1+1)-Evolutionary Algorithm (EA), and Genetic Algorithm (GA) for the GIP. Using the concepts of Markov chain Coupling, this article proves that the Markov chains associated with the randomized local search mixes rapidly, i.e., the mixing time is bounded above by O(n2 ). Experimentally, RLS outperforms (1+1)-EA and GA on the permutation matrix space.

AB - —Graph isomorphism problem (GIP) is a class NP Problem and is a well-studied problem in graph and complexity theory. It is still an open problem, whether GIP is in class P or NP-complete. In the literature, no meta-heuristics are applied to GIP. However, few studies in the literature show that the meta-heuristic algorithms are applied to the subgraph isomorphism problem, which is a known NP-Complete problem and extension of GIP. This article proposes a new search space called permutation matrix space for GIP. Two search space elements are neighbors if one is obtained from the other by swapping any two distinct rows. The work shows that the magnification of permutation matrix space is bounded below by n/2. Magnification is one of the main structural properties of a search graph which implies the number of arcs going out from any cut-set in the search graph. The article studies the performance of Randomized Local Search (RLS), (1+1)-Evolutionary Algorithm (EA), and Genetic Algorithm (GA) for the GIP. Using the concepts of Markov chain Coupling, this article proves that the Markov chains associated with the randomized local search mixes rapidly, i.e., the mixing time is bounded above by O(n2 ). Experimentally, RLS outperforms (1+1)-EA and GA on the permutation matrix space.

UR - http://www.scopus.com/inward/record.url?scp=85130762974&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85130762974&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:85130762974

SN - 1816-093X

VL - 30

JO - Engineering Letters

JF - Engineering Letters

IS - 2

ER -