Hello,
I have two questions that have been bugging me recently. The first is about the number of spanning forests in a graph and the second is about enumerating these with edge labels.
Q1: I am aware of Kirchhoff's Matrix-Tree theorem regarding the number of spanning trees in a graph. I was wondering if there is a generalization to this theorem that counts the number of spanning k-forests in a graph. What I am mostly interested in is this: is there a method of finding the number of k-forests in a graph by taking a determinant of some matrix?
Q2: Suppose you label each edge as $e_{i,j}$ meaning that you are taking the undirected edge from $v_i$ to $v_j$ in the graph. Then in the Laplacian matrix if you plug in the sum of $e_{i,j}$'s instead of $\deg(v_i)$ and $-e_{i,j}$ instead of -1 when that edge connects vertices $i$ and $j$, you get the combinatorial Laplacian. Taking the determinant of a minor of this matrix gives the Kirchhoff polynomial which is an enumeration of the spanning trees of the graph, where each monomial contains the variables for all the edges in the given tree. My question is whether we can generalize this to spanning forests.
Best Answer
Two points:
(1) There is a result which is very similar to this. Let $G$ be a graph. Let $A$ be the matrix whose rows and columns are indexed by the vertices of $G$, where $A_{ij}$ is negative the number of edges from $i$ to $j$, for $i \neq j$, and where $A_{ii} = \lambda_i + \deg_i(G)$. Then the coefficient of $\lambda_{i_1} \cdots \lambda_{i_k}$ in $\det A$ is the number of spanning forests of $G$ with $k$ components, such that $i_1$, $i_2$, ... and $i_k$ are in separate components. Notice that the case $k=1$ is the matrix tree theorem: The coefficient of $\lambda_{i_1}$ is clearly the determinant of the adjacency matrix of $G$, with the $i_1$-st rows and column deleted. Basically any proof of the matrix-tree theorem should prove this as well.
If you set all the $\lambda_i$'s equal to each other, then the coefficient of $\lambda^k$ in $\det(A)$ will be the weighted number of $k$-spanning-forests, where the weight of a forest with components $T_1$, $T_2$, ..., $T_k$ is $\prod |T_i|$. (Because that is the number of ways to choose $k$ vertices, one in each component.) Perhaps this is good enough for your purposes.
(2) It is highly unlikely that there is a reasonable formula which gives you an exact count. More precisely, counting spanning forests is a #P-complete problem. See On the Computational Complexity of the Jones and Tutte Polynomials and note that counting spanning forests is equivalent to evaluating Tutte at $(1,2)$. This means that, assuming $P \neq NP$, there is no polynomial algorithm to count spanning forests. Now, "reasonable formula" is not a precisely defined notion, but I suspect that anything you would consider reasonable would give a polynomial time algorithm. In particular, note that computing an $n \times n$ determinant, all of whose entries have at most $n$ digits, is polynomial time.