minimal edge cover for bipartite graphs?

[arm...@yahoo.com]

Are there known efficient algorithms to solve the
following edge cover problem?

Given a bipartite graph, each of its edges has a
weight. Find a set of edges, which covers the
vertices of the graph and its total weight is minimal.

A paper I am reading, suggests that this problem
can be reduced to weighted matching, for which
there are known good algorithms. How does one
perform this "reduction"?

-arman

Sent via Deja.com http://www.deja.com/
Before you buy.

[Luis Goddyn]

Minimal Edge Cover is polytime, even for nonbipartite graphs. The polyhedron
has been well studied (eg. Hurkens, C. A. J., On the diameter of the edge cover
polytope, J. Combin. Theory Ser. B 51 (1991), 271--276).

An fast algorithm for bipartite graphs arizes as an easy modification of the Hungarian
(primal-dual) matching algorithm. The modification accounts for the observation that
dual varibles can never be negative, and the complementary slackness condition that
only nodes with dual value zero can be covered by more than one edge.
I emphasize the differences in capital letters in the following outline.
Here the bipartition is $V = X \cup Y$.

When growing an "alternating tree" $T$ from an uncovered node $x \in X$, we may
augment the edge cover (along the $v,x$-path in $T$) as soon $T$ acquires either
(1) a node $v \in Y$ which is either currently uncovered, or
(2) A NODE $v \in Y$ WHOSE DUAL VARIABLE EQUALS ZERO, or
(3) A NODE $v \in X$ WHICH IS COVERED AT LEAST TWICE.
In case (2), the augmentation will leave $v$ covered by at least two edges.
In case (3), $v$ is left covered by one fewer edge. In all cases $x$ becomes covered.

If $T$ contains no such $v$ then we perform a dual variable change for the nodes
in $T$ as usual, but the dual change is also limited by nonnegativity.
That is, the dual variable change results in either some reduced cost going to zero
OR SOME DUAL VARIABLE GOING TO ZERO. In the former case we resume growing the tree
as usual, in the latter case, we immediatly augment as per (2).

arm...@yahoo.com wrote:
>
> Are there known efficient algorithms to solve the following edge cover problem?
>
> Given a bipartite graph, each of its edges has a
> weight. Find a set of edges, which covers the
> vertices of the graph and its total weight is minimal.

> [etc...]
> -arman

--- _____._____
Luis Goddyn email: god...@math.sfu.ca /| /|\ |\
Dept. of Math. and Stats. http://www.sfu.ca/~goddyn /_|__/ | \__|_\
Simon Fraser University tel: (604) 291-4699 | |__|_|_|__| |
Burnaby BC V5A 1S6 fax: -4947 | / | ^ | \ |
CANADA |/___|/ \|___\|

[arm...@my-deja.com]

Here's the answer to my question which I received from Christoph Spreen
<ch.s...@sun01.sts.tu-harburg.de>.

The solution can be found in:

Editor: Mikhail J. Atallah
Handbook on Algorithms and Theory of Computation
1998, CRC Press, ISBN: 0849326494

The basic idea is as follows:

Given a weighted bipartite graph G = (V1, V2, E, W) and searching for
a cost-minimal edge-cover K, build a new bipartite graph G' = (V1', V2',
E', W'):

* V1' := V1, V2' := V2, E' := E, W' := W (so far a copy of G)
* V1' gets also copies of V2
* V2' gets also copies of V1 (so |V1'| = |V2'|)
* Connect all newly inserted nodes with each other with zero-edges (or
better: edges that are "nearly" zero)
* Connect each node v in V1' with its copy in V2'. The weighting of
this new edge should be the minimum of weightings of all edges
incident to v in the original graph G.

Now you can use any matching algorithm (e.g. wmatch), to find the
_minimal_ matching in the new bipartite graph.

After using the matching algorithm, nodes which are matched with their
copies, correspond to the edge incident on the node in the original
graph with the minimal weight.