[Math] the “true” minimum spanning forest of a connected graph

graph theorynp-completetrees

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).

Best Answer

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)$.