A new approach and faster exact methods for the maximum common subgraph problem

Abstract

The Maximum Common Subgraph (MCS) problem appears in many guises and in a wide variety of applications. The usual goal is to take as inputs two graphs, of order m and n, respectively, and find the largest induced subgraph contained in both of them. MCS is frequently solved by reduction to the problem of finding a maximum clique in the order mn association graph, which is a particular form of product graph built from the inputs. In this paper a new algorithm, termed “clique branching,” is proposed that exploits a special structure inherent in the association graph. This structure contains a large number of naturally-ordered cliques that are present in the association graph’s complement. A detailed analysis shows that the proposed algorithm requires O((m+1)n) time, which is a superior worst-case bound to those known for previously-analyzed algorithms in the setting of the MCS problem.

Research sponsored by the Laboratory Directed Research and Development Program of Oak Ridge National Laboratory, managed by UT-Battelle, LLC, for the U. S. Department of Energy under Contract DE–AC05–00OR22725, by the U.S. National Science Foundation under grant CCR–0311500, by the Office of Naval Research under grant N00014–01–1–0608, and by the U.S. Department of Energy’s Genomes to Life program under the ORNL-PNNL project “Exploratory Data Intensive Computing for Complex Biological Systems.”