5
$\begingroup$

I have got two sets of elements and a pruned graph of bipartite edges with weights assigned to each edge. I need to find the minimal set of edged with the minimum cost covering all nodes from both sets. Multiple assignment is ok as long as every element is covered.

I find the Assignment Problem is the closest to the problem I am trying to solve. Again with the exception that multiple assignments in both ways are permitted.

I tried using the Hungarian Algorithm. The problem is that it tries to avoid multiple assignments. Anyone has any hints on a way for solving this problem?

4 Answers 4

2

You are looking for a edge cover (that happens to be different from vertex cover or minimal spanning tree) of your graph.

I do not know if there are generalization of the algorithm proposed in the wikipedia page (maximum matching + greedy) that works also in your case (you have different costs for each edge).

  • 0
    I find the [Assignment Problem](http://en.wikipedia.org/wiki/Assignment_problem) is the closest to the problem I am trying to solve. Again with the exception that multiple assignments in both ways are permitted.2012-11-22
0

Sounds like a case for minimal spanning tree. edit: No, it is not. Sorry. Thank you carlop.

  • 0
    Not sure of that. My graph is a bipartie whose edges have always first element from first set and second element from second set.2012-11-22
0

I am simply elaborating on Hendrik Jan's answer. A minimum spanning tree on a graph has the minimum number of edges needed to cover all nodes (a tree with $n$ nodes has $n-1$ edges). This satisfies your minimal edges constraint. And the minimum spanning tree algorithm ensures that out of all such spanning trees, any one with the least total edge weights is generated. This will satisfy your second condition.

It does not matter if your graph is bipartite or not, this works regardless. A spanning tree will simply select edges from the existing edges, such that all nodes are covered. If the edges form a bipartite graph, so be it.

It might generate "multiple assignments" but that is acceptable to you.

Popular algorithms for finding the minimum spanning tree for a given graph are Kruskal's algorithm and Prim's algorithm. In fact, this being a bipartite graph, it might be possible to optimize these algorithms for the bipartite case, so that they run faster than their upper bounds for general graphs.

  • 0
    @carlop I guess I was implicitly assuming connectedness. You are right, this should be weighted edge cover as you mention in your answer.2012-11-23
0

This problem may be reduced to assignment problem. But it requires to notice that costs for each edge must first be modified:

cost[i][j] = min(cost[i][j], min_out_cost[i] + min_in_cost[j]) 

This means that instead of using edge u-v, one may use 2 cheapest edges, one coming out of u, the other coming to v.

Why? Partial explanation is that because when you have the optimal solution and consider an edge that connects vertice u and v, where u has more than one edge selected, than this must be minimal edge for v.