Given an undirected graph G with $n$ nodes, we can compute its number of spanning trees in polynomial time using Kirchhoff's matrixtree theorem. Now consider a more complicated setting, in which each of the $n$ nodes in the graph has $m$ versions and each version has different connectivity with the other nodes of the graph. The connectivity between different versions of different nodes can be encoded with a 4dimensional array A
where A[i][k][j][l]
is 1 iff the $k$th version of node $i$ is connected by an edge with the $l$th version of node $j$. Therefore we have $m^n$ different graphs. We want to compute the total number of spanning trees in these $m^n$ graphs. The bruteforce approach that computes the number of spanning trees in each graph separately would require exponential time. My question is whether we can derive a simplified form of the total number such that it can be computed in polynomial time.
1
$\begingroup$
$\endgroup$

$\begingroup$ It has been shown that the problem is #Pcomplete and therefore is unlikely to be solved in polynomial time: cstheory.stackexchange.com/a/27638/13406 $\endgroup$ – took Dec 1 '14 at 2:37