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.


Your Answer

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

Browse other questions tagged or ask your own question.