4
$\begingroup$

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.

$\endgroup$
  • $\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 Shor Nov 29 '14 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 Shor Nov 29 '14 at 21:33
7
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.