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 we can derive a simplified form of the total number such that it can be computed in polynomial time.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ It has been shown that the problem is #P-complete and therefore is unlikely to be solved in polynomial time: cstheory.stackexchange.com/a/27638/13406 $\endgroup$– tookCommented Dec 1, 2014 at 2:37
Add a comment
|