<p>Given an undirected weighted graph, G, where all the weights are non-zero positive numbers, my algorithm must produce a sub-graph G' that satisfies the following constraints:</p>

<ol>
<li>G' must include all the vertices of G.</li>
<li>All vertices must be connected to at least one vertex of G'.  In other words the edges of G' must <a href="https://en.wikipedia.org/wiki/Edge_cover" rel="nofollow noreferrer">cover</a> all the vertices of G'.</li>
<li>The total weights of all edges in G' must be as low as possible.</li>
</ol>

<p>In other words, this is the minimum weighted edge cover problem.</p>

<p>So, my question is, in terms of time complexity with respect to the number of vertices and edges, what is the fastest known algorithm for finding the correct answer?</p>

<p>What I've done so far:</p>

<p>I've found some resources online, but they often seem to say contradictory things.</p>

<p>I was able to find one post that pointed out that this problem can be reformulated as a maximum matching problem (see <a href="https://cstheory.stackexchange.com/questions/14690/reducing-a-minimum-cost-edge-cover-problem-to-minimum-cost-weighted-bipartie-per">here</a>).</p>

<p>In that case, I've found references to Edmond's Algorithm, which can run in O(V^2*E) or O(V^3) time.  There are references to improved versions of this algorithm, but as far as I can tell, these only deal with unweighted graphs, not weighted ones.  So, as far as the known solutions go, is O(V^2*E) or O(V^3) time complexity the best we can get?</p>

CC BY-SA 3.0
2016-10-19T01:50:44.943Z
Did you look in Schrijver's book on combinatorial optimization?
Chandra Chekuri
CC BY-SA 3.0
2016-10-19T02:51:45.203Z
I don't have access to it without buying it, at the moment, but I've found a similar textbook I can get online for free through my University.  I'll be reading through it later today.
Nimrand
<graph-theory><graph-algorithms><optimization><time-complexity>
Fastest Algorithm for the Minimum Edge Covering Problem
Nimrand
# Fastest Algorithm for the Minimum Edge Covering Problem

(Asked by: username_0 on 2016-10-19)

Given an undirected weighted graph, G, where all the weights are non-zero positive numbers, my algorithm must produce a sub-graph G' that satisfies the following constraints:

1. G' must include all the vertices of G.
2. All vertices must be connected to at least one vertex of G'. In other words the edges of G' must [cover](https://en.wikipedia.org/wiki/Edge_cover) all the vertices of G'.
3. The total weights of all edges in G' must be as low as possible.

In other words, this is the minimum weighted edge cover problem.

So, my question is, in terms of time complexity with respect to the number of vertices and edges, what is the fastest known algorithm for finding the correct answer?

What I've done so far:

I've found some resources online, but they often seem to say contradictory things.

I was able to find one post that pointed out that this problem can be reformulated as a maximum matching problem (see [here](https://cstheory.stackexchange.com/questions/14690/reducing-a-minimum-cost-edge-cover-problem-to-minimum-cost-weighted-bipartie-per)).

In that case, I've found references to Edmond's Algorithm, which can run in O(V^2\*E) or O(V^3) time. There are references to improved versions of this algorithm, but as far as I can tell, these only deal with unweighted graphs, not weighted ones. So, as far as the known solutions go, is O(V^2\*E) or O(V^3) time complexity the best we can get?

**Tags:** graph-theory, graph-algorithms, optimization, time-complexity
> **Comments:**
> **username_1**: Did you look in Schrijver's book on combinatorial optimization?  
> **username_0**: I don't have access to it without buying it, at the moment, but I've found a similar textbook I can get online for free through my University.  I'll be reading through it later today.  

---

## 0 answers

