Given an undirected graph G with $n$ nodes, we can compute its number of spanning trees in polynomial time using Kirchhoff's matrix-tree 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 4-dimensional 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 brute-force approach that computes the number of spanning trees in each graph separately would require exponential time. My question is whether there is a polynomial-time algorithm.
-
$\begingroup$ Why don't we simplify the problem? Choose $t$ edges which share no vertices, and ask to count the total number of spanning trees in the $2^t$ graphs which have all possible subsets of these $t$ edges. Is there a way to do this in polynomial time? $\endgroup$– Peter ShorNov 29, 2014 at 15:31
-
$\begingroup$ Actually, there is. This is equivalent to counting each spanning tree $2^k$ times, where $k$ is the number of edges they contain from this subset. Now, just make a multigraph where you replace each of these edges with two edges and use Kirchhoff's theorem. $\endgroup$– Peter ShorNov 29, 2014 at 21:33
1 Answer
Can't this problem be used to compute the permanent of a 0-1 matrix? Since permanent is a #P-complete problem (harder than NP), there is very unlikely to a polynomial-time algorithm.
Suppose you have an $n \times n$ matrix $M$ that you want to compute the permanent of. Construct a graph on $2n+1$ vertices, where there is a special vertex $v$ which has one copy, and $n$ of the vertices $x_1$ $\ldots$, $x_n$ have only one copy, while the remaining $n$ vertices $y_1$, $\ldots$, $y_n$, have $n$ copies each. On the $i$'th copy of vertex $y_j$, connect it to $x_i$. Connect the $i$'th copy of $y_j$ to $v$ if and only if the entry $M(i,j) = 1$.
Now, for $x_i$ to be in the spanning tree, you must have chosen the $i$'th copy of $y_j$ for some $j$. So we must have a permutation $\pi$, where we have chosen the $\pi(j)$ copy of vertex $y_j$. For this permutation to be a spanning tree we must have $M(\pi(j), j) = 1$ for each vertex $j$. This shows that the permutation $\pi$ yields a spanning tree if and only if it contributes $1$ to the permanent of $M$. Thus, the number of spanning trees is the permanent of $M$.
