<p>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. </p>

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

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

CC BY-SA 3.0
2014-11-29T21:48:21.103Z
2014-11-30T23:39:10.707Z
2014-11-30T23:39:10.707Z
Peter Shor 
<p>Given an undirected graph G with $n$ nodes, we can compute its number of spanning trees in polynomial time using <a href="http://en.wikipedia.org/wiki/Kirchhoff%27s_theorem" rel="nofollow">Kirchhoff's matrix-tree theorem</a>. 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 <code>A</code> where <code>A[i][k][j][l]</code> 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.</p>

CC BY-SA 3.0
2014-11-29T15:31:28.473Z
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?
Peter Shor 
CC BY-SA 3.0
2014-11-29T21:33:19.273Z
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.
Peter Shor 
<graph-theory><graph-algorithms>
Total number of spanning trees of a set of graphs
took
# Total number of spanning trees of a set of graphs

(Asked by: username_0 on 2014-11-29)

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](http://en.wikipedia.org/wiki/Kirchhoff%27s_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.

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_1**: 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?  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_1 on 2014-11-29. Score: 7 | Accepted 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$.


---

