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'$?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
