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

  • $\begingroup$ How are you defining weight? If it is such that adding edges must increase the weight then the minimal spanning set of edges touching each vertex would automatically have no cycles. $\endgroup$ Commented May 10, 2015 at 5:17
  • $\begingroup$ Thanks Jair, I amended my question. Given that my two questions are equivalent (right?) what is known about the minimum weight edge-cover? $\endgroup$
    – Yaron
    Commented May 11, 2015 at 17:04

1 Answer 1


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

  • $\begingroup$ Great answer, except that the Hungarian algorithm only applies to bipartite graphs. For general maximum weight matching, one can use Edmonds' primal-dual algorithm. $\endgroup$
    – Guyslain
    Commented Oct 25, 2021 at 11:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .