Maximum weight matching and submodular functions

Question

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?

Answer 1

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.