Subset of a bipartite graph with maximal number of minimal unmatched vertices

Question

Given a bipartite graph $G = (U \sqcup V, E)$ with sets of vertices $U$ and $V$ and edge set $E \subseteq U \times V$, a matching $M$ is a subset of $E$ whose edges have no common vertices: for all $(u, v)$ and $(u', v') \in M$, $u = u'$ or $v = v'$ implies $(u, v) = (u', v')$. A maximum matching is a matching containing the maximum number of edges. It is immediate that a maximum matching is a matching achieving the minimal number of unmatched vertices, where I say that $u \in U$ is unmatched in $M$ if there is no $(u', v') \in M$ such that $u = u'$, and likewise for $v \in V$. Hence, the minimal number of unmatched vertices in $G$ over all possible matchings of $G$, that I write $f(G)$, can be computed by finding a maximum matching, which can be done in polynomial time with, e.g., the Hopcroft-Karp algorithm.

I now consider the following problem: from a bipartite graph $G = (U \sqcup V, E)$, what is the maximum, over all subsets $U'$ of $U$, of $f(G_{|U'})$? By $G_{|U'}$ I mean the bipartite graph which is the restriction of $G$ to $U'$, namely $G_{|U'} = (U' \sqcup V, \{(u, v) \in E \mid u \in U'\})$.

Is this problem NP-hard, or can it be solved in PTIME? On the one hand it seems related to set cover or exact cover which are NP-hard, but on the other hand the subproblem of maximum matching is PTIME and maybe there is a clever way to identify what is the worst subset.

To motivate this problem, here is a rephrasing in terms of assignments of agents to tasks. $U$ is a set of tasks, $V$ a set of agents, and $E$ indicates which agents can perform which tasks. A matching is a way of assigning tasks to agents such that each agent does at most one task and each task is done by at most one agent. The cost measure is the number of unmatched vertices, namely the number of undone tasks plus the number of unoccupied agents. I want to know what is my worst possible cost in this sense, over all subsets of the tasks (think of $U$ as a set of possible tasks from which an arbitrary subset will be requested, and $V$ as a fixed set of agents that I cannot adjust but which I can allocate freely once a subset has been requested).

To see why this problem is not trivial, observe that choosing the empty subset $\emptyset \subseteq U$ yields a cost of $|V|$ (the cost of leaving all agents unoccupied), the complete subset $U \subseteq U$ yields a certain cost and may be the worst if e.g. $|U|$ is much larger than $|V|$, but in general my best solution may be to choose a subset of $U$ which retains the tasks than can be done by only few agents (so that many of them will have to remain undone as each of those agents can do only one task) but would not retain the tasks that can be done by otherwise unoccupied agents (so that those agents remain unoccupied and contribute to the cost).

If this problem is in PTIME, I am also interested to know if the following weighted version is also PTIME: each vertex and each edge has a weight, the cost of a matching is the sum of the weights of the unmatched vertices plus the sum of the weights of the retained edges, and I want again to find the subset of $U$ with the worst minimal cost in this sense. In the vocabulary of the assignment problem, this means that each task and each agent has an individual cost of remaining undone or unoccupied, and assigning a task to an agent is not free anymore but carries a certain cost indicated on the edge.

Answer 1

The problem is in $P$ by reducing the problem to submodular minimization.

Let $v(A)$ be defined as the size of the maximum matching in $G_{|A}$. $v$ is submodular. One way to see this is convert the problem to a max flow problem, and use the fact that the set function $c(U)=$ max flow from $U$ to $t$ defined over $V\setminus \{t\}$ is submodular.

I will use $f(A)$ to mean the $f(G_{|A})$ in your notation.

$f(A) = |A| + |V| - 2v(A)$. $|V|$ is a constant, so we can maximize over $f(A)-|V| = |A| - 2v(A)$, which is the same as minimize $g(A) = 2v(A)-|A|$. $g$ is a submodular function(difference of submodular and modular function), and you can apply any polynomial time submodular function minimization algorithm.

This can be extended to weighted case if weighted analogue of $v(A)$ is submodular.