5
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ There's a simple reduction: for each node $s \in S$, add $k$ new nodes $t_1,\dots,t_k$ and edges $(s,t_i)$, where $k$ is at least the size of the maximum matching (e.g., $k \ge n$). Then any maximum matching in the new graph is a maximum matching in the original graph that contains $S$: the new edges essentially force the optimal solution to include all nodes in $S$. However, this potentially blows up the size of the graph by a factor of $|S|$, i.e., potentially by as much as $\Theta(n)$... so it doesn't preserve the running time of those basic algorithms. Perhaps it's possible to do better? $\endgroup$
    – D.W. ♦
    Jul 31, 2015 at 0:25

2 Answers 2

Reset to default
2
$\begingroup$

Assume the maximum matching problem is $U-V$ matching, and $S\subset U$.

  1. 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.
  2. 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)$)

Improve this answer
$\endgroup$
0
$\begingroup$

It can be done in $\widetilde{O}(m^{10/7})$ time, by reducing to network flow.

As a warmup, suppose we know the max matching you're seeking has size $k$. Then let's build a flow graph by adding three nodes to your original graph: we'll add a source node $s$, a second node $s'$, and a sink node $t$. Then, we'll add some edges with unit capacity: $k-|S|$ parallel edges $s \to s'$, an edge $s \to v$ for each node $v \in S$, an edge $s' \to w$ for each node $w$ on the left-hand side such that $w\notin S$, and an edge $x\to t$ for each node $x$ on the right-hand side. Now find the maximum flow in this graph. This will give you the matching you want: your matching corresponds to a legal flow of capacity $k$, and any legal flow of capacity $k$ corresponds to a matching of size $k$ that matches every vertex in $S$ (since the only way to get $k$ flow out of $s$ is to saturate every edge out of $s$, and in particular to send one unit of flow to each vertex in $S$; that flow has to go somewhere, so that means every vertex of $S$ is matched).

So, if we knew $k$, this would find the matching you want. Also, the running time would be $\widetilde{O}(m^{10/7})$, as Madry's algorithm can compute maximum flows in that running time.

Of course, in real life we don't know $k$ a priori. However, we can use binary search to find it. This increases the running time by a $\lg(n)$ factor, which is absorbed in the $\widetilde{O}$ running time; the total running time remains $\widetilde{O}(m^{10/7})$.

I realize this doesn't answer whether $O(m \sqrt{n})$ or $O(n^\omega)$ is attainable. It seems possible that the same considerations which lead to a $O(m \sqrt{n})$ time for computing maximum flows in bipartite matching instances might also lead to a $O(m \sqrt{n})$ time for the kind of graph I outlined above, but I don't know whether this is indeed the case or not.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think the solution of sub problem for given k does not maintains the ~O(n^10/7) complexity, as it only holds for unit capacity networks, but the edge s→s′ breaks the property. $\endgroup$
    – Terence Hang
    Aug 31, 2015 at 15:36
  • $\begingroup$ Thanks, @TerenceHang. I've edited my answer accordingly. My edited answer should maintain the $\widetilde{O}(m^{10/7})$ complexity (note: $\widetilde{O}(m^{10/7})$, not $\widetilde{O}(n^{10/7})$). Madry's algorithm does allow parallel edges, so it's easy to arrange that all edges have unity capacity in the new graph I build. See edited answer for details. $\endgroup$
    – D.W. ♦
    Aug 31, 2015 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.