3
$\begingroup$

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

$\endgroup$
  • $\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$ – Jair Taylor May 10 '15 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 May 11 '15 at 17:04
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.