COUNTING SUBGRAPHS VIA HOMOMORPHISMS.

We introduce a generic approach for counting subgraphs in a graph. The main idea is to relate counting subgraphs to counting graph homomorphisms. This approach provides new algorithms and unifies several well-known results in algorithms and combinatorics, including the recent algorithm of Björklund, Husfeldt, and Koivisto for computing the chromatic polynomial, the classical algorithm of Kohn et al. for counting Hamiltonian cycles, Ryser's formula for counting perfect matchings of a bipartite graph, and color-coding-based algorithms of Alon, Yuster, and Zwick. By combining our method with known combinatorial bounds, ideas from succinct data structures, partition functions, and the color coding technique, we obtain the following new results. The number of optimal bandwidth permutations of a graph on n vertices excluding a fixed graph as a minor can be computed in time 2n+o(n)), in particular, in time O(2nn³) for trees and in time 2n+O(√n) for planar graphs. Counting all maximum planar subgraphs, subgraphs of bounded genus, or more generally subgraphs excluding a fixed graph M as a minor can be done in 2O(n) time. Counting all subtrees with a given maximum degree (a generalization of counting Hamiltonian paths) of a given graph can be done in time 2O(n). A generalization of Ryser's formula is, Let G be a graph with an independent set of size I. Then the number of perfect matchings in G can be found in time O(2n-ℓn³). Let H be a graph class excluding a fixed graph M as a minor. Then the maximum number of vertex disjoint subgraphs from H in a graph G on n vertices can be found in time 2O(n). In order to show this, we prove that there exists a constant CM depending only on M such that the number of nonisomorphic n-vertex graphs in H is at most cnM. Let F be a k-vertex graph of treewidth t and let G be an n-vertex graph. A subgraph of G isomorphic to F (if one exists) can be found in O(4.32k⋅k⋅t⋅nt+1) expected time using O(log k ⋅ nt+1 space. [ABSTRACT FROM AUTHOR]