patternMinor
Maximum bipartite matching when some nodes must be matched
Viewed 0 times
nodesmaximummatchedmustbipartitesomewhenmatching
Problem
Consider the problem of finding a maximum cardinality bipartite matching under the additional condition that some set $S$ of nodes (all lying on the same side of the bipartition) must be matched.
Can this problem be reduced to (ordinary) bipartite matching? Bipartite matching can be solved in $O(m \sqrt{n})$ by Hopcroft Karp or $O(n^{\omega})$ where $\omega$ is the exponent of matrix multiplication due to a recent result, or $\widetilde{O}(m^{10/7})$ in terms of the number of edges m. Do these running times carry over to this problem? I think Hopcroft-Karp can produce the same running time with some modifications, but am not sure about the others; so I'm wondering if a simple reduction to matching exists -- this would allow one to bypass an analysis of the above papers.
Can this problem be reduced to (ordinary) bipartite matching? Bipartite matching can be solved in $O(m \sqrt{n})$ by Hopcroft Karp or $O(n^{\omega})$ where $\omega$ is the exponent of matrix multiplication due to a recent result, or $\widetilde{O}(m^{10/7})$ in terms of the number of edges m. Do these running times carry over to this problem? I think Hopcroft-Karp can produce the same running time with some modifications, but am not sure about the others; so I'm wondering if a simple reduction to matching exists -- this would allow one to bypass an analysis of the above papers.
Solution
Assume the maximum matching problem is $U-V$ matching, and $S\subset U$.
Since an augmenting path never turns a matched vertex into unmatched vertex, the maximum matching found by above algorithm meets the requirement.
Using Hopcroft Karp algorithm, the complexity is $O(m\sqrt{n})$.
I don't know if the $O(n^{\omega})$ or $\tilde{O}(m^{10/7})$ algorithm works. But basically any maximum matching algorithm that based on augmentation works. And for those unit capacity network flow algorithms, it also works as long as it accepts an initial feasible flow and arguments along it, taking the lower capacity bound into account. (ie. never augment back through edges $s \to x (x\in S)$)
- Find maximum $S-V$ matching. If the result equals $|S|$, then it is a feasible matching in original $U-V$ matching problem. Othewise, no matching meets the requirement.
- Using the feasible matching got in previous step as basis, improve it by augmentation, thus computing maximum $U-V$ matching.
Since an augmenting path never turns a matched vertex into unmatched vertex, the maximum matching found by above algorithm meets the requirement.
Using Hopcroft Karp algorithm, the complexity is $O(m\sqrt{n})$.
I don't know if the $O(n^{\omega})$ or $\tilde{O}(m^{10/7})$ algorithm works. But basically any maximum matching algorithm that based on augmentation works. And for those unit capacity network flow algorithms, it also works as long as it accepts an initial feasible flow and arguments along it, taking the lower capacity bound into account. (ie. never augment back through edges $s \to x (x\in S)$)
Context
StackExchange Computer Science Q#44890, answer score: 2
Revisions (0)
No revisions yet.