We are given a graph G with N(numbered 1 to N) nodes and M edges.

Let’s create a big graph B with NK nodes (numbered 1 through NK) and MK edges. B consists of K copies of G ― formally, for each k (0≤k≤K−1) and each edge between nodes u and v in G, there is an edge between nodes u+kN and v+kN in B.

We take the complement of the graph B and name it H.

The task is to calculate the number of spanning trees in H.

Note : The maximum number of nodes in graph G is 20. The maximum value of K is 10^8. The graph G doesn’t have any self-loops or multiple-edges.

My approach : When the value of K is less than 40, I am being able to apply Kirchoff’s Matrix Tree theorem with a complexity of O(N^3)(Gaussian elimination gives us a O(n^3) algorithm to compute determinants). However,my solution doesn’t scale for very large graphs which are formed for high values of K. I am figuring I should be able to derive a formula to calculate the number of spanning trees because of the repeated copies of small graph G. But because of my limited mathematical knowledge, I am not being able to converge to a formula.

Any help would be greatly appreciated.