<p>The problem is in $P$ by reducing the problem to submodular minimization. </p>

<p>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.</p>

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

<p>$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.</p>

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

CC BY-SA 3.0
2016-01-20T01:02:46.887Z
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!
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-04-04T18:54:42.197Z
Needing this some years later, I take back the claim that $v$ is submodular for the reason I gave -- I think I was confused in what I wrote. I'm not sure at the moment of how this is proven, but an analogous claim is given in Example 1.3 of McCormick, "Submodular function minimization", https://theory.stanford.edu/~jvondrak/data/submod-tutorial-1.pdf So I'm not claiming it's not true, but still have to understand how the proof of this claim really works.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-05-06T11:13:51.957Z
As it turns out, a proof of the claim is in Megiddo, "Optimal Flows in Networks with Multiple Sources and Sinks", Mathematical Programming 7, 1974 (https://theory.stanford.edu/~megiddo/pdf/optflows.pdf), Lemma 3.2 (ii). (Thanks to @M.Monet for locating this!)
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2016-01-19T00:54:27.493Z
2016-01-19T00:54:27.493Z
Chao Xu
<p>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 <em>matching</em> $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 <em>maximum matching</em> is a matching containing the maximum number of edges. It is immediate that a maximum matching is a matching achieving the minimal number of <em>unmatched</em> 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 <a href="https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm" rel="nofollow">Hopcroft-Karp algorithm</a>.</p>

<p>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'\})$.</p>

<p>Is this problem NP-hard, or can it be solved in PTIME? On the one hand it seems related to <a href="https://en.wikipedia.org/wiki/Set_cover" rel="nofollow">set cover</a> or <a href="https://en.wikipedia.org/wiki/Exact_cover" rel="nofollow">exact cover</a> 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.</p>

<p>To motivate this problem, here is a rephrasing in terms of <a href="https://en.wikipedia.org/wiki/Assignment_problem" rel="nofollow">assignments</a> 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).</p>

<p>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).</p>

<p>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.</p>

CC BY-SA 3.0
2013-12-18T20:19:00.547Z
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.
David Richerby
CC BY-SA 3.0
2013-12-19T01:05:08.820Z
Ah, you're right, I fixed the title, now it should be correct. Thanks a lot for pointing this out!
Antoine Amarilli 'a3nm'
<ds.algorithms><graph-algorithms><co.combinatorics><optimization><matching>
Subset of a bipartite graph with maximal number of minimal unmatched vertices
Antoine Amarilli 'a3nm'
# Subset of a bipartite graph with maximal number of minimal unmatched vertices

(Asked by: username_0 on 2013-12-18)

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](https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_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](https://en.wikipedia.org/wiki/Set_cover) or [exact cover](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Assignment_problem) 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.

**Tags:** ds.algorithms, graph-algorithms, co.combinatorics, optimization, matching

> **Comments:**
> **username_1**: 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.  
> **username_0**: Ah, you're right, I fixed the title, now it should be correct. Thanks a lot for pointing this out!  

---

## 1 answers

### Answer by username_2 on 2016-01-19. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: 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!  
> **username_0**: Needing this some years later, I take back the claim that $v$ is submodular for the reason I gave -- I think I was confused in what I wrote. I'm not sure at the moment of how this is proven, but an analogous claim is given in Example 1.3 of McCormick, "Submodular function minimization", https://theory.stanford.edu/~jvondrak/data/submod-tutorial-1.pdf So I'm not claiming it's not true, but still have to understand how the proof of this claim really works.  
> **username_0**: As it turns out, a proof of the claim is in Megiddo, "Optimal Flows in Networks with Multiple Sources and Sinks", Mathematical Programming 7, 1974 (https://theory.stanford.edu/~megiddo/pdf/optflows.pdf), Lemma 3.2 (ii). (Thanks to @M.Monet for locating this!)  

---

