The complexity of counting homeomorphs (Q1058852): Difference between revisions

In this note we show that, for any finite nontrivial family \({\mathcal H}\) of graphs, the problem of finding the number of subgraphs of a graph which are homeomorphic from a member of \({\mathcal H}\) is {\#}P-complete. From this it follows that the problems of counting the paths, circuits, or minimal nonplanar subgraphs of a graph are all {\#}P-complete.