3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The title says "least number of unmatched edges" but the question says "minimal number of unmatched vertices". I assume you mean the latter, since deleting all of $U$ deletes all edges so is a trivial solution to the former. $\endgroup$ – David Richerby Dec 18 '13 at 20:19
  • $\begingroup$ Ah, you're right, I fixed the title, now it should be correct. Thanks a lot for pointing this out! $\endgroup$ – a3nm Dec 19 '13 at 1:05
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks very much! I didn't know about submodular functions, but your idea looks good to me. When reading I assumed that $A$ ranges over subsets of $U$. I checked manually that $v$ is submodular by saying that if $X \subseteq Y \subseteq U$ and $x \in U \backslash Y$ then, if adding $x$ to $Y$ can increase the size of the maximum matching (i.e., $x$ can be matched, i.e., a maximum matching with $Y$ leaves free a neighbor of $x$) then the same holds with $X$ as $X \subseteq Y$. I then checked that $g$ is submodular using $g(S) + g(T) \geq g(S \cup T) + g(S \cap T)$ (it simplifies). Thanks again! $\endgroup$ – a3nm Jan 20 '16 at 1:02

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.