# Maximum matching in a bipartite graph

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'$$?

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.