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?

  • 3
    $\begingroup$ What do you think? Have you tried proving / disproving it? $\endgroup$ – Yuval Filmus May 2 '16 at 18:22
  • $\begingroup$ 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. $\endgroup$ – George Octavian Rabanca May 2 '16 at 18:33
  • 2
    $\begingroup$ This is true for unweighted case, as it can be reduced to min-cuts. It's not obvious how to prove the weighted version... $\endgroup$ – Chao Xu May 3 '16 at 3:08
  • $\begingroup$ Consider $K_{2,2}$ with edge weights 1,1,1,2. $\endgroup$ – András Salamon May 3 '16 at 13:47
  • 1
    $\begingroup$ @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. $\endgroup$ – George Octavian Rabanca May 3 '16 at 23:27

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

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.

  • $\begingroup$ 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$. $\endgroup$ – Andrew Morgan Jul 20 '16 at 2:57

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.