Lecture notes in computer science vol:5211 pages:520-535
Principles and Practice of Knowledge Discovery in Databases location:Antwerp, Belgium date:15 - 19 September 2008
The frequent connected subgraph mining problem, i.e., the problem of listing all connected graphs that are subgraph isomorphic to at least a certain specified number of elements of a database of transaction graphs, cannot be solved in output polynomial time in the general case. If, however, the transaction graphs are restricted to trees then the problem becomes tractable. In this paper, we generalize the positive complexity result on trees to graphs of bounded treewidth. In particular, we show that for this class of transaction graphs, frequent connected subgraphs can be listed with incremental polynomial delay. Since subgraph isomorphism remains NP-complete for bounded treewidth graphs, the positive complexity result of this paper implies that efficient frequent pattern mining is possible even for computationally hard pattern matching operators.