<p><strong>Definition</strong>. For a given finite set $A$, a set function $f:2^A \rightarrow \mathbb{R}$ is submodular if for any $X, Y \subseteq A$ it holds that: 
$$
f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y).  
$$</p>

<p><strong>Lemma</strong>
Given a bipartite graph $G = (A \cup B, E)$ with positive edge weights, let $f: 2^A \rightarrow \mathbb{R}^+$ be the function that maps $S\subseteq A$ to the value of the maximum weight matching in $G[S \cup B]$.  Then $f$ is submodular.</p>

<p><strong>Proof.</strong>
Fix two sets $X, Y \subseteq A$ and let $M_\cap$ and $M_\cup$ be two matchings for the graphs $G[(X\cap Y) \cup B]$ and $G[(X \cup Y) \cup B]$ respectively.  To prove the lemma is enough to show that it is possible to partition the edges in $M_\cap$ and $M_\cup$ into two disjoint matchings $M_X$ and $M_Y$ for the graphs $G[X\cup B]$ and $G[Y\cup B]$ respectively.</p>

<p>The edges of $M_\cap$ and $M_\cup$ form a collection of alternating paths and cycles.  Let $\mathcal{C}$ denote this collection and observe that no cycle of $\mathcal{C}$ contains vertices from $X\setminus Y$ or $Y\setminus X$.   This holds because $M_\cap$ does not match those vertices.</p>

<p>Let $\mathcal{P}_X$ be the set of paths in $\mathcal{C}$ with at least one vertex in $X \setminus Y$ and let $\mathcal{P}_Y$ be the set of paths in $\mathcal{C}$ with at least one vertex in $Y \setminus X$.  Two such paths are depicted in the figure below.</p>

<p><a href="https://i.sstatic.net/6hJhi.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/6hJhi.png" alt="enter image description here"></a></p>

<p><strong>Claim 1.</strong>
$\mathcal{P}_X \cap \mathcal{P}_Y = \emptyset$.  </p>

<p>Assume by contradiction that there exists a path $P \in \mathcal{P}_X \cap \mathcal{P}_Y$.  Let $x$ be a vertex in $X\setminus Y$ on path $P$ and similarly let $y$ be a vertex in $Y \setminus X$ on path $P$.  Observe that since neither $x$ nor $y$ belong to $X \cap Y$ they do not belong to the matching $M_\cap$ by definition, and therefore they are the endpoints of the path $P$.  Moreover, since both $x$ and $y$ are in $A$, the path $P$ has even length and since it is an alternating path, either the first or last edge belongs to $M_\cap$. Therefore $M_\cap$ matches either $x$ or $y$, which contradicts the definition and proves the claim.</p>

<p>Let 
$$M_X = (\mathcal{P}_X \cap M_\cup) \cup ( (\mathcal{C} \setminus \mathcal{P}_X) \cap M_\cap)$$ 
and 
$$M_Y = (\mathcal{P}_X \cap M_\cap) \cup ( (\mathcal{C} \setminus \mathcal{P}_X) \cap M_\cup).$$
It is clear that $M_X \cup M_Y = M_\cap\cup M_\cup$  and $M_X \cap M_Y = M_\cap \cap M_\cup$.  To prove the theorem it remains to show that $M_X$ and $M_Y$ are valid matchings for $G[X\cup B]$ and $G[Y\cup B]$ respectively.
To see that $M_X$ is a valid matchings for $G[X\cup B]$ observe first that that no vertex of $Y \setminus X$ is matched by $M_X$ since $\mathcal{P}_X$ does not intersect $Y \setminus X$ by Claim 1, and $M_\cap$ does not intersect $Y \setminus X$ by definition.  Therefore, $M_X$ only uses vertices of $X \cup B$.  Second observe that every vertex $x\in X$ is matched by at most one edge of $M_X$ since otherwise $x$ belongs to either two edges of $M_\cup$ or two edges of $M_\cap$, contradicting the definition.  This proves that $M_X$ is a valid matching for $G[X\cup B]$;  showing that $M_Y$ is a valid matchings for $G[Y\cup B]$ is similar.</p>

CC BY-SA 3.0
2016-07-20T02:57:54.003Z
This looks great! As a minor suggestion: the definitions of $M_X$ and $M_Y$ aren't symmetric, so your final claim that "$M_Y$ ... is similar" isn't immediate. It's more clear (I think) if you let $\mathcal{C'} \doteq \mathcal{C} \setminus \mathcal{P}_X \setminus \mathcal{P}_Y$ denote the connected components not touching any vertex in $X \Delta Y$, and then set $M_X = (\mathcal{P}_X \cap M_\cup) \cup (\mathcal{P}_Y \cap M_\cap) \cup (\mathcal{C'} \cap M_\cap)$ and $M_Y$ to be the same with $X$ and $Y$ swapped and then the last $M_\cap$ changed to $M_\cup$.
Andrew Morgan
CC BY-SA 3.0
2016-07-19T22:06:07.733Z
2016-07-19T22:06:07.733Z
George Octavian Rabanca
<p>Given a bipartite graph $G = (U \cup V, E)$ with positive weights let $f: 2^U \rightarrow \mathbb{R}$ with $f(S)$ equal to the maximum weight matching in the graph $G[S\cup V]$.</p>

<p>Is it true that $f$ is a submodular function?</p>

CC BY-SA 3.0
2016-05-02T18:22:07.340Z
What do you think? Have you tried proving / disproving it?
Yuval Filmus
CC BY-SA 3.0
2016-05-02T18:33:51.110Z
Intuitively it seems like it should be true but I couldn't prove it.  Also I think that if it's true it should be a well known result but I couldn't find a reference.
George Octavian Rabanca
CC BY-SA 3.0
2016-05-03T03:08:37.207Z
This is true for unweighted case, as it can be reduced to min-cuts. It's not obvious how to prove the weighted version...
Chao Xu
CC BY-SA 3.0
2016-05-03T13:47:19.240Z
Consider $K_{2,2}$ with edge weights 1,1,1,2.
András Salamon
CC BY-SA 3.0
2016-05-03T14:03:19.183Z
@AndrásSalamon  Is this supposed to be a counter example?  If $x$ and $y$ are the vertices of $U$ and $y$ is the vertex connected to the edge of weight 2...   Then $f(\emptyset) = 0$, $f({x}) = 1$, $f({y}) = 2$ and $f({x, y}) = 3$, a submodular function.
George Octavian Rabanca
CC BY-SA 3.0
2016-05-03T22:41:06.967Z
@GeorgeOctavianRabanca no, it was a hint.  The graph might as well be complete bipartite, with nonnegative weights, adding zero weight edges where necessary to achieve this.  Now $f(S \cup T)=f((S\setminus T)\cup(S\cap T)\cup(T\setminus S))\le f(S\setminus T)+f(S\cap T)+f(T\setminus S)+f(S\cap T)-f(S\cap T)= f(S)+f(T)-f(S\cap T)$.
András Salamon
CC BY-SA 3.0
2016-05-03T23:27:21.787Z
@AndrásSalamon It seems like in the last step you assume that $f$ is additive, which is not true.  The maximum matching of $S\cap T$ might use vertices that have already been used by both matching of $S \setminus T$ and $T \setminus S$.  I have a proof for this now but is definitely more involved than this.
George Octavian Rabanca
CC BY-SA 3.0
2016-05-04T07:34:01.593Z
@GeorgeOctavianRabanca You are right, $f$ is not additive.
András Salamon
<matching><submodularity>
Maximum weight matching and submodular functions
George Octavian Rabanca
# Maximum weight matching and submodular functions

(Asked by: username_0 on 2016-05-02)

Given a bipartite graph $G = (U \cup V, E)$ with positive weights let $f: 2^U \rightarrow \mathbb{R}$ with $f(S)$ equal to the maximum weight matching in the graph $G[S\cup V]$.

Is it true that $f$ is a submodular function?

**Tags:** matching, submodularity

> **Comments:**
> **username_1**: What do you think? Have you tried proving / disproving it?  
> **username_0**: Intuitively it seems like it should be true but I couldn't prove it.  Also I think that if it's true it should be a well known result but I couldn't find a reference.  
> **username_2**: This is true for unweighted case, as it can be reduced to min-cuts. It's not obvious how to prove the weighted version...  
> **username_3**: Consider $K_{2,2}$ with edge weights 1,1,1,2.  
> **username_0**: @AndrásSalamon  Is this supposed to be a counter example?  If $x$ and $y$ are the vertices of $U$ and $y$ is the vertex connected to the edge of weight 2...   Then $f(\emptyset) = 0$, $f({x}) = 1$, $f({y}) = 2$ and $f({x, y}) = 3$, a submodular function.  
> **username_3**: @GeorgeOctavianRabanca no, it was a hint.  The graph might as well be complete bipartite, with nonnegative weights, adding zero weight edges where necessary to achieve this.  Now $f(S \cup T)=f((S\setminus T)\cup(S\cap T)\cup(T\setminus S))\le f(S\setminus T)+f(S\cap T)+f(T\setminus S)+f(S\cap T)-f(S\cap T)= f(S)+f(T)-f(S\cap T)$.  
> **username_0**: @AndrásSalamon It seems like in the last step you assume that $f$ is additive, which is not true.  The maximum matching of $S\cap T$ might use vertices that have already been used by both matching of $S \setminus T$ and $T \setminus S$.  I have a proof for this now but is definitely more involved than this.  
> **username_3**: @GeorgeOctavianRabanca You are right, $f$ is not additive.  

---

## 1 answers

### Answer by username_0 on 2016-07-19. Score: 2 | Accepted answer

**Definition**. For a given finite set $A$, a set function $f:2^A \rightarrow \mathbb{R}$ is submodular if for any $X, Y \subseteq A$ it holds that:
$$
f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y).
$$

**Lemma**
Given a bipartite graph $G = (A \cup B, E)$ with positive edge weights, let $f: 2^A \rightarrow \mathbb{R}^+$ be the function that maps $S\subseteq A$ to the value of the maximum weight matching in $G[S \cup B]$. Then $f$ is submodular.

**Proof.**
Fix two sets $X, Y \subseteq A$ and let $M\_\cap$ and $M\_\cup$ be two matchings for the graphs $G[(X\cap Y) \cup B]$ and $G[(X \cup Y) \cup B]$ respectively. To prove the lemma is enough to show that it is possible to partition the edges in $M\_\cap$ and $M\_\cup$ into two disjoint matchings $M\_X$ and $M\_Y$ for the graphs $G[X\cup B]$ and $G[Y\cup B]$ respectively.

The edges of $M\_\cap$ and $M\_\cup$ form a collection of alternating paths and cycles. Let $\mathcal{C}$ denote this collection and observe that no cycle of $\mathcal{C}$ contains vertices from $X\setminus Y$ or $Y\setminus X$. This holds because $M\_\cap$ does not match those vertices.

Let $\mathcal{P}\_X$ be the set of paths in $\mathcal{C}$ with at least one vertex in $X \setminus Y$ and let $\mathcal{P}\_Y$ be the set of paths in $\mathcal{C}$ with at least one vertex in $Y \setminus X$. Two such paths are depicted in the figure below.

[![enter image description here](https://i.sstatic.net/6hJhi.png)](https://i.sstatic.net/6hJhi.png)

**Claim 1.**
$\mathcal{P}\_X \cap \mathcal{P}\_Y = \emptyset$.

Assume by contradiction that there exists a path $P \in \mathcal{P}\_X \cap \mathcal{P}\_Y$. Let $x$ be a vertex in $X\setminus Y$ on path $P$ and similarly let $y$ be a vertex in $Y \setminus X$ on path $P$. Observe that since neither $x$ nor $y$ belong to $X \cap Y$ they do not belong to the matching $M\_\cap$ by definition, and therefore they are the endpoints of the path $P$. Moreover, since both $x$ and $y$ are in $A$, the path $P$ has even length and since it is an alternating path, either the first or last edge belongs to $M\_\cap$. Therefore $M\_\cap$ matches either $x$ or $y$, which contradicts the definition and proves the claim.

Let
$$M\_X = (\mathcal{P}\_X \cap M\_\cup) \cup ( (\mathcal{C} \setminus \mathcal{P}\_X) \cap M\_\cap)$$
and
$$M\_Y = (\mathcal{P}\_X \cap M\_\cap) \cup ( (\mathcal{C} \setminus \mathcal{P}\_X) \cap M\_\cup).$$
It is clear that $M\_X \cup M\_Y = M\_\cap\cup M\_\cup$ and $M\_X \cap M\_Y = M\_\cap \cap M\_\cup$. To prove the theorem it remains to show that $M\_X$ and $M\_Y$ are valid matchings for $G[X\cup B]$ and $G[Y\cup B]$ respectively.
To see that $M\_X$ is a valid matchings for $G[X\cup B]$ observe first that that no vertex of $Y \setminus X$ is matched by $M\_X$ since $\mathcal{P}\_X$ does not intersect $Y \setminus X$ by Claim 1, and $M\_\cap$ does not intersect $Y \setminus X$ by definition. Therefore, $M\_X$ only uses vertices of $X \cup B$. Second observe that every vertex $x\in X$ is matched by at most one edge of $M\_X$ since otherwise $x$ belongs to either two edges of $M\_\cup$ or two edges of $M\_\cap$, contradicting the definition. This proves that $M\_X$ is a valid matching for $G[X\cup B]$; showing that $M\_Y$ is a valid matchings for $G[Y\cup B]$ is similar.

> **Comments:**
> **username_4**: This looks great! As a minor suggestion: the definitions of $M_X$ and $M_Y$ aren't symmetric, so your final claim that "$M_Y$ ... is similar" isn't immediate. It's more clear (I think) if you let $\mathcal{C'} \doteq \mathcal{C} \setminus \mathcal{P}_X \setminus \mathcal{P}_Y$ denote the connected components not touching any vertex in $X \Delta Y$, and then set $M_X = (\mathcal{P}_X \cap M_\cup) \cup (\mathcal{P}_Y \cap M_\cap) \cup (\mathcal{C'} \cap M_\cap)$ and $M_Y$ to be the same with $X$ and $Y$ swapped and then the last $M_\cap$ changed to $M_\cup$.  

---

