1
$\begingroup$

I am reading on how solving maximum flow (Ford-Fulkerson) can be also used to solve unweighted bipartite graph matching problem. I think I don't understand the essence of this problem, because to me it seems trivial.

The method of solving the problem says to convert the original bipartite graph into a network, by creating a Source and Sink vertices, directing all edges towards the Sink and setting all edges' capacity to 1. Then I should run Ford-Fulkerson. Fair enough.

My question is, can't I just do this linearly? (Obviously not, but I don't see why). The goal of the problem seems to be to find a maximum matching in a complete bipartite graph - i.e. the maximum number of edges between the two "sections" of the graph that do not share any vertices.

To illustrate, see this picture

enter image description here

  • In the first graph the maximum matching will be 2 - any of the two vertices on the right may only be connected to a single vertex on the left. Since the edges are unweighted, it doesn't really matter which?
  • Similarly in the second graph, the matching will again be just 2.

Can you tell me where am I thinking wrong? I don't understand where the complexity of the problem comes from.

And sorry if any of the terms were used incorrectly, I am not studying CS in English. Thanks

|cite|improve this question
$\endgroup$
  • $\begingroup$ Do you realize that not all vertices on the right need to be connected to all vertices on the left? (then it will still be a bipartite graph). edit: I see now that you say "complete bipartite graph". Then your solution would be correct. $\endgroup$ – Albert Hendriks Jun 1 '16 at 19:34
  • $\begingroup$ It might also be that the input is guaranteed to be a (complete) bipartite graph, but that your algorithm just needs to figure out how many nodes are on the left and how many on the right. $\endgroup$ – Albert Hendriks Jun 1 '16 at 19:56
5
$\begingroup$

I am reading on how [...] to solve unweighted bipartite graph matching problem. [...] The goal of the problem seems to be to find a maximum matching in a complete bipartite graph

No, the goal of the problem is to find a maximum matching in any unweighted bipartite graph.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Then it seems my professor's text has an error in it. This explains it then, thanks! $\endgroup$ – Martin Melka Jun 2 '16 at 8:04
  • $\begingroup$ @MartinMelka maybe the confusion comes from the problem of finding a maximum-weight matching in a bipartite graph with weighted edges. Then, it is indeed without loss of generality to assume that the graph is complete, since you can add the missing edges with weight 0. $\endgroup$ – Erel Segal-Halevi Feb 11 at 17:09

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.