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.
본 논문은 그래프의 유사도를 비교하는 기준이 될 수 있는 최대 부분트리 문제를 다루고 있다. 이 문제는 주어진 두 그래프에서 동형인 부분트리 중 그 크기가 최대인 것을 찾는 문제이다. 본 문제에서 제시한 알고리즘은 이진 정수 계획 모형을 통해 주어진 두 개의 그래프에서 트리 구조를 갖는 차수열 동일 그래프를 찾아낸 후, 그 두 개의 트리가 동형인지 확인하는 절차를 반복함으로써 최대 부분트리를 찾게 된다. 본 논문에서 제시한 이진 정수 계획 모형은 대응되는 노드의 차수가 동일해야한다는 조건부 제약을 포함하고 있으며, 이를 표현하기 위해 도입해야 하는 큰 수 M의 영향으로 문제의 크기가 커졌을 때, 최적해까지의 수렴이 매우 늦는 단점이 존재한다. 이러한 현상을 해소하기 위해 Codato와 Fischetti (2006) 가 제안한 수리 모형 분할 기법을 이용하였다. 또한 트리 구조에 대한 제약식의 많은 수 때문에 모든 제약식을 포함한 상태로 문제를 해결하는 것은 비효율적이라 할 수 있는데, 일부의 제약식만으로 문제를 해결할 수 있게 하기 위해 절단 평면 방법을 이용하였다. 최종적으로 이진 정수 계획 모형은 주어진 그래프의 두 부분 트리를 찾아내게 되는데, 이들이 동형인지 여부는 Aho, Hopcroft와 Ullman (1974) 이 제안한 AHU-알고리듬을 통해서 다항시간 내에 확인할 수 있다. 따라서 찾아낸 트리구조가 동형일 때까지 위의 절차를 반복적으로 수행함으로써, 알고리즘은 결국 동형인 부분트리를 찾아낼 수 있게 된다. 랜덤하게 발생시킨 그래프에 대해 실험을 실시한 결과, 기존의 최대 부분 그래프에 대한 이진 정수 계획모형에 비교했을 때, 적당한 크기의 예제에서 더 빠른 시간안에 최적해를 찾아 낼 수 있었다.
