(An) algorithm for the maximum common subtree problem using the degree sequence

Abstract

In this thesis, we consider the maximum common subtree problem (MCST) which can be a notion of graph similarity. The MCST problem is defined as follows. Given two graphs $G_1 = (V_1, E_1)$ and $G_{2} = (V_{2}, E_{2})$ with $|V_1|=|V_2|$ , find subgraphs of $G_1$ and $G_2$ having tree structure which are isomorphic with the maximum number of edges. To solve this problem, we use the property of the degree sequence equivalence between two graphs, which means that the two graphs have the same degree sequences when they are isomorphic. First, we define the maximum degree sequence equivalence subgraph problem and propose a 0-1 integer programming formulation for this problem. Our algorithm uses this formulation to detect the degree sequence equivalent subgraphs having tree structure. This formulation contains the conditional constraints having big-M coefficients to represent the degree equivalence of matched pair of nodes. Hence, the formulation becomes hard to solve for large instances. To deal with this, we apply the decomposition technique and combinatorial Benders’ cuts proposed by Codato and Fischetti (2006). Moreover, we also implement the cutting plane method to handle the exponential number of constraints related to the sub-tour elimination inequalities. After we find the two trees, our algorithm checks whether detected trees are isomorphic or not. The tree isomorphism is checkable by the AHU-algorithm in polynomial time. Overall algorithm recursively solve the formulation until isomorphic two graphs are detected. Otherwise, our algorithm solves the formulation again after excluding current solution. Computational results show that this algorithm performs relatively well in solving of random instances of moderate size compared to the earlier integer programming model for the maximum common edge subgraph problem.