An Upper Bound for Minimum True Matches in Graph Isomorphism with Simulated Annealing
This addresses a performance gap in meta-heuristic algorithms for graph isomorphism, an NP-hard problem with applications in various domains, but it is incremental as it focuses on explaining inefficiency rather than proposing a new solution.
The paper tackles the inefficiency of simulated annealing for graph matching, showing it is unlikely to approach optimal solutions, with experimental results indicating a low probability (e.g., 0.02) of achieving more than three correct matches in sample graphs.
Graph matching is one of the most important problems in graph theory and combinatorial optimization, with many applications in various domains. Although meta-heuristic algorithms have had good performance on many NP-Hard and NP-Complete problems, for this problem there are not reported superior solutions by these algorithms. The reason of this inefficiency has not been investigated yet. In this paper we show that simulated annealing as an stochastic optimization method is unlikely to be even close to the optimal solution for this problem. In addition to theoretical discussion, the experimental results also verified our idea; for example, in two sample graphs, the probability of reaching to a solution with more than three correct matches is about $0.02$ in simulated annealing.