4
$\begingroup$

Given a bipartite graph $G=(V_1 \cup V_2, E)$ and a set $V' \in (V_1 \cup V_2)$. What is the complexity of finding a maximum matching in $G$ that uses only $x$ vertices from $V'$?

| cite | improve this question | | | | |
$\endgroup$
5
$\begingroup$

Set $V_i' = V_i \cap V'$. You can solve this by finding the maximum matching using at most $k$ vertices from $V_1'$ and at most $x-k$ from $V_2'$ for all $k \in [0, x]$. This in turn can be found with maximum flow.

To find this maximum matching, we modify the usual reduction to maximum flow. Let $s$ be the source and $t$ the sink. Let $l$ and $r$ be auxiliary vertices. Add an edge from $s$ to $l$ with capacity $k$, and an edge from $r$ to $t$ with capacity $x-k$. All other edges will have capacity $1$. Add an edge from $l$ to every $x \in V_1'$, and from $s$ to every $x \in V_1 \setminus V_1'$. Add an edge from every $y \in V_2'$ to $r$, and from every $y \in V_2 \setminus V_2'$ to $t$. For $(x, y) \in E$, add an edge from $x$ to $y$. Now the maximum flow gives a maximum matching using at most $k$ vertices in $V_1'$ and $x-k$ in $V_2'$.

We can thus solve the problem in $\mathcal{O}(x \cdot M)$ where $M$ is the complexity of maximum flow. The maximum flow problems are very similar, so we can improve on this.

We can increase or decrease the capacity of any edge by $1$ while maintaining the maximum flow in $\mathcal{O}(|E|)$. First calculate the maximum matching using no vertices in $V'$. Then, increase the capacity of the edge from $s$ to $l$ by $x$. Then at every step increase the capacity of the edge from $r$ to $t$ and decrease the capacity of the edge from $s$ to $l$ while maintaining a maximum flow. Output the largest matching produced. The complexity will be $\mathcal{O}(|E| \sqrt{|V|} + x \cdot |E|)$ if we use Dinic to find the initial bipartite matching.

| cite | improve this answer | | | | |
$\endgroup$

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.