Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth

摘要

The subgraph isomorphism problem, that of finding a copy of one graph in another, has proved to be intractable except when certain restrictions are placed on the inputs. In this paper, we introduce a new property for graphs along with an associated graph class (a generalization on bounded degree graphs) and extend the known classes of inputs for which polynomial-time subgraph isomorphism algorithms are attainable. In particular, if the removal of any set of at most k vertices from an n-vertex graph results in O(klogn) connected components, we say that the graph is a log-bounded fragmentation graph. We present a polynomial-time algorithm for finding a subgraph of H isomorphic to a graph G when G is a log-bounded fragmentation graph and H has bounded treewidth; these results are extended to handle graphs of locally bounded treewidth (a generalization of treewidth) when G is a log-bounded fragmentation graph and has constant diameter.