Timeline for Number of spanning forests in a graph
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 17, 2019 at 20:56 | comment | added | David E Speyer | @Nubok A spanning forest, in the context of my answer and the original question, is a forest which contains all the vertices of the original graph. | |
| Mar 17, 2019 at 18:47 | comment | added | Nubok | > This means that, assuming P≠NP, there is no polynomial algorithm to count spanning forests. Perhaps I miss something important, but in my opinion, a spanning forest is just a spanning tree in each component. So we just have to find all components of G (easy), count the number of spanning trees in each component (Kirchhoff's tree theorem) and multiply these numbers. So I think you rather mean "This means that, assuming P≠NP, there is no polynomial algorithm to count forests." | |
| Jun 1, 2011 at 10:25 | vote | accept | Aleks Vlasev | ||
| Jun 1, 2011 at 5:45 | comment | added | Aleks Vlasev | (2) As for enumeration, I'm not sure that enumeration is the right word in this case. What I meant is that I need a polynomial where each monomial is a product of variables $e_{i,j}$, each associated to one of the edges in the spanning forest. I wonder if I just use the same idea used in constructing graph polynomials - replace the degree with a sum of edge variables of edges attached to the vertex, i.e. $A_{i,i} = \lamba_i + \sum e_{i,k}$, where $k$ runs over all indices except $i$. As for the -1 entries, what if we replace them with $-e_{i,j}$. Would this give us what we need? | |
| Jun 1, 2011 at 5:37 | comment | added | Aleks Vlasev | (1) Ooh! That is very useful! Does this matrix have a name? Where can I read about it? I compared the results of using this matrix with some results from a brute force code that I have and they match 1 to 1. Thank you very much David! Also, I think that if I put the same lambda on two vertices, I will be able to get the number of spanning forests such that these two vertices are in the same tree. Is this true? | |
| May 31, 2011 at 22:59 | history | answered | David E Speyer | CC BY-SA 3.0 |