Finding the maximum common subgraph of a partial k-tree and a graph with a polynomially bounded number of spanning trees

The maximum common subgraph problem is known to be NP-hard, although it has often been applied to various areas. In the field of molecular biology, we can reduce the problem space by analyzing the structures of chemical compounds. In doing so, we have found that the tree-width of chemical compounds are bounded by a constant, and that the possible spanning trees of any compound is polynomially bounded. We present a polynomial time algorithm for finding the maximum common connected induced subgraph of a degree-bounded partial k-tree and a connected graph, the number of whose possible spanning trees is polynomial. (C) 2004 Elsevier B.V. All rights reserved.