After application of the pruning rules described above, we obtain a pruned induced graph, containing a (typically small) subset of the edges in the original induced graph. In favorable cases, the remaining edges contain only one minimal edge cover. However, typically, there may be several minimal edge covers possible for the pruned induced graph. We now describe how we select one of these minimal edge covers.
We first approximate the fair cost of every edge e that
remains after pruning by its lower bound 
. (We could have
also use the upper bound, or an average of both bounds, since this is
only an estimate.) Then, given these constant estimated costs, we
compute a minimum-cost edge cover by reducing the edge cover problem
to a bipartite weighted matching problem, as suggested in
[&make_named_href('',
"node21.html#combopt","[PS82]")]. Since the weighted matching problem can be solved
using standard techniques, we do not present the details in this
paper, noting only that given a bipartite graph with n nodes and e
edges, the weighted matching problem can be solved in time O(ne) .
For our application, e is the number of edges that remain in the
induced graph after pruning.