Minimum of submodular function over family of subsets

Theorem1

Let $L$ and $L^{'}$ are two lattices. If $f : L \to R$ is a submodular function and $P : L^{'} \to 2^{L}$ is a function with the property that if $X \in P (A)$ and $Y \in P (B)$ , then $X \land Y \in P (A \land B)$ and $X \lor Y \in P (A \lor B)$ . $f_{P} : L^{'} \to R$ defined as $f_{P} (X) = Y \in P (X) min f (Y)$ is submodular.

Proof

Let $X^{*} = arg min_{Y \in P (X)} f (Y)$ , note since $X^{*} \in P (X)$ and $Y^{*} \in P (Y)$ , we have $X^{*} \lor Y^{*} \in P (X \lor Y)$ and $X^{*} \lor Y^{*} \in P (X \land Y)$ . $f_{P} (X) + f_{P} (Y) = f (X^{*}) + f (Y^{*}) \geq f (X^{*} \lor Y^{*}) + f (X^{*} \land Y^{*}) \geq f ((X \lor Y)^{*}) + f ((X \land Y)^{*}) = f_{P} (X \lor Y) + f_{P} (X \land Y)$

This is quite useful, for starters, it proves that we can create a monotone submodular function from any submodular function.

Theorem2

Let $f : 2^{V} \to R$ be a submodular function, then $f_{*}, f^{*} : 2^{V} \to R$ defined as $f_{*} (X) = min {f (Y) ∣ Y \subset X} f^{*} (X) = min {f (Y) ∣ X \subset Y}$ are monotone and submodular.

A practical application is to generalize the cut function. Consider for a directed graph graph $G = (V, E)$ . We would define $δ^{+} (A)$ to be the set of out going edges from $A$ to $V ∖ A$ . $f = ∣ δ^{+} ∣$ is a submodular function. An alternate definition for $f$ is the minimum number of edges to be removed so there is no path from $A$ to $V ∖ A$ .

A simple generalization is when we only care about $T \subset V$ . We can define $f_{T} (A)$ to be the minimum number of edges to be removed so there is no path from $A$ to $T ∖ A$ . Amazingly(or not not surprisingly, depending on your intuition), $f_{T}$ is also a submodular function by invoking the next theorem, which is a direct corollary of our first theorem.

Theorem3

Let $f : 2^{V} \to R$ be a submodular function, then $f_{T} : 2^{T} \to R$ defined as $f_{T} (X) = min {f (Y) ∣ Y \subset X, T ∖ X \subset V ∖ Y}$ is submodular.

Posted by Chao Xu on 2014-08-13.

Tags: submodular.