What is the "true" minimum spanning forest of a connected graph?

1.6k Views Asked by At

Normally, a minimum spanning forest of a graph G is defined as the union of minimum spanning trees of each of its components. This definition is a generalization of the minimum spanning tree of a connected graph to a graph with arbitrary number of components. A spanning tree has to be connected (i.e. not a multi-component forest).

What is however the forest F of minimal weight of a weighted graph G, such that every vertex in G has an incident edge in F?

I found a partial answer, this is actually a variant of the minimum edge cover. So, rephrasing the question, what is known about the minimum weight edge-cover of a general weighted graph G?(weights are positive reals assigned to edges and the graphs weight is their sum).

1

There are 1 best solutions below

1
On

In this answer on cstheory, David Eppstein explains how to reduce an instance of the minimum-weight edge cover problem to a maximum-weight matching:

[Given a minimum-weight edge cover,] if we assign each vertex to an edge that covers it, some edges will cover both of their endpoints (forming a matching $M$) and others will cover only one of their endpoints (and must be the minimum weight edge adjacent to the covered endpoint). If we let $c_v$ be the cost of the minimum weight edge incident to vertex $v$, and $w_e$ be the weight of $e$, then the cost of a solution is $$\sum_{v\in G} c_v + \sum_{(u,v)\in M} (w_{(u,v)}-c_u-c_v).$$ The first sum doesn't depend on the choice of the cover, so the problem becomes one of finding a matching that maximizes the total weight, for edge weights $c_u+c_v-w_{(u,v)}$.

This reduces the problem to finding a maximum-weight matching with the revised weights (the remaining edges in the cover are chosen greedily as described above); this can be found using, for example, the Hungarian algorithm with runtime $O(V^2E)$.