ntherner's blog

[Question] Multi-distributing Maximum Bipartite Matching
By ntherner, 3 years ago, In English

Recently, I attempted a problem. It doesn't matter which. A portion of problem could've been easily solved using Maximum Bipartite Matching. I, however, disregarded the portion of the statement implying it could've been solved with this algorithm for some time, and had found myself trying to solve the following problem (using flows, which turned out to be underwhelmingly difficult):

Given a graph $$$G = (V = (L, R), E)$$$, then find a maximal set of edges such that each element from $$$R$$$ has at least an incident edge and each element from $$$L$$$ has exactly one incident edge.

Is this problem solvable in any way? If yes, how, if no, why?

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Is G bipartite? If so I think it can be modeled as a flow with minimum capacity constraints

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider that is the case. Could you please detail how do you model the flow network?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      In that case, build the classical flow network for bipartite matching, where you add a source S and a sink T, connect S to each node in L and connect each node in R to T. At this point, you'd usually limit the capacities of the new edges you inserted to 1, but let's change that so that the edges coming out of S have both a capacity of 1 and a demand of 1 (forcing each node in L to have exactly one outgoing edge) and edges going to T have a demand of 1 and infinite capacity (that's the at least constraint).

      After finding a maximum flow on this graph (for example, like this) you can take all the original edges with positive flow as your solution.

      → Reply