A Two-Stage Discrete Optimization Method for Largest Common Subgraph Problems

摘要

A novel combinatorial optimization algorithm called 2-stage discrete optimization method (2DOM) is proposed for the largest common subgraph problem (LCSP) in this pa- per. Given two graphs G = (V_1,E_1) and H = (V_2,E_2), the goal of LCSP is to find a subgraph G′ = (V′_1,E′_1) of G and a subgraph H′= (V′_2,E′_2) of H such that G′ and H′ are not only isomorphic to each other but also their number of edges is maximized. The two graphs G′ and H′ are isomorphic when │V′_1│=│V′_2│ and│E′_1│=E′_2│, and there exists one-to-one ver- tex correspondence f: V′_1 —＞V′_2 such that {u,v} ∈ E′_1 if and only if {f(u), f(v)} ∈ E′_2. LCSP is known to be NP-comp1ete in general. The 2DOM consists of a construction stage and a re- finement stage to achieve the high solution quality and the short computation time for large size difficult combinatorial optimiza- tion problems. The construction stage creates a feasible initial solution with considerable quality, based on a greedy heuristic method. The refinement stage improves it keeping the feasibility, based on a random discrete descent method. The performance is evaluated by solving two types of randomly generated 1200 LCSP instances with a maximum of 500 vertices for G and 1000 vertices for H. The simulation result shows the superiority of 2DOM to the simulated annealing in terms of the solution quality and the computation time.