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

Nobuo FUNABIKI  Junji KITAMICHI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E82-D   No.8   pp.1145-1153
Publication Date: 1999/08/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
Keyword: 
common subgraph,  isomorphic,  NP-complete,  greedy method,  discrete descent method,  simulated annealing,  

Full Text: PDF(396.2KB)>>
Buy this Article




Summary: 
A novel combinatorial optimization algorithm called 2-stage discrete optimization method (2DOM) is proposed for the largest common subgraph problem (LCSP) in this paper. Given two graphs G=(V1, E1) and H=(V2, E2), the goal of LCSP is to find a subgraph G'=(V1', E1') of G and a subgraph H'=(V2', E2') 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 |V1'|=|V2'| and |E1'|=|E2'|, and there exists one-to-one vertex correspondence f: V1' V2' such that {u, v} E1' if and only if{f(u), f(v)} E2'. LCSP is known to be NP-complete in general. The 2DOM consists of a construction stage and a refinement stage to achieve the high solution quality and the short computation time for large size difficult combinatorial optimization 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.