# Maximum weight matching and submodular functions

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?

• What do you think? Have you tried proving / disproving it? – Yuval Filmus May 2 '16 at 18:22
• 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 May 2 '16 at 18:33
• 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 May 3 '16 at 3:08
• Consider $K_{2,2}$ with edge weights 1,1,1,2. – András Salamon May 3 '16 at 13:47
• @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 May 3 '16 at 23:27

## 1 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.

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.

• 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 Jul 20 '16 at 2:57