Approximation Algorithm (9): Survivable Network Design

Survivable network design is the problem of building a network that remains connected even after some edges are removed.

Let’s assume that there is a given undirected graph $G = (V,E)$ with costs $c_e \ge 0$ $\forall e \in E$. Now, let’s define connectivity requirments $r_{ij} \in \mathbb{Z}^{+} \cup \{0\}$ for all pairs of vertices $i,j \in V$, where $i \neq j$. Then problem is a find a minimum cost set of edges $F \subset E$ such that $G’ = (V,F)$ has $r_{ij}$ edge distinct paths to connecting $i$ and $j$.

Now, we can make a integer programming over this and it is like follow. “Minimize $\sum\limits_{e \in E} c_e x_e$ such that $\sum\limits_{e \in \delta(S)} x_e \ge \max\limits_{i \in S, j \not\in S} r_{ij}$ $\forall S \subset V$, $x_e \in \{0,1\}$” which $\delta(S)$ denotes the set of edges between $S$ and $V - S$. Notice that if there is $r_{ij}$ edge distinct paths, we can make a flow of value $r_{ij}$ between $i$ and $j$. Then, there should be a mincut that corresponding to that flow from the network flow theory. As a result, constraint above should be fulfilled. It’s the same in the opposite direction. If we have a such min-cut then we have such flow either.

Now, we can do a linear programming relaxation like we did in the set cover. “Minimize $\sum\limits_{e \in E} c_e x_e$ such that $\sum\limits_{e \in \delta(S)} x_e \ge \max\limits_{i \in S, j \not\in S} r_{ij}$ $\forall S \subset V$, $0 \le x_e \le 1$”. We can solve this LP in polynomial time using the ellipsoid method. We construct a separation oracle as follows.

Make a graph that consists of $G = (V,E)$ and set capacity of $E$ as $x_e$.
Solve the network flow problem between all pair $i$ and $j$ such that $i \neq j$ and $i,j \in V$.
If there is a flow such that the value of flow $f_{ij}$ is less than $r_{ij}$ then it’s an infeasible solution otherwise it is feasible.

Now, let’s define $f(S) = \max\limits_{i \in S, j \not\in S} r_{ij}$. Then problem will be shifted to “Minimize $\sum\limits_{e \in E} c_e x_e$ such that $\sum\limits_{e \in \delta(S)} x_e \ge f(S)$ $\forall S \subset V$, $0 \le x_e \le 1$”.

If we make $f(S)$ as so then $f(S)$ is so-called weakly supermodular. To be a weakly supermodular, there are some requirements.

$f(\emptyset) = f(U) = 0$ for ground set $U$.
one of $f(A) + f(B)$ $\le$ $f(A \cap B) + f(A \cup B)$ or $f(A) + f(B)$ $\le$ $f(A - B) + f(B - A)$ should be true.

Proof is like follow. First, it is trivial that $f(\emptyset) = f(V) = 0$ because there is no such an edge between $V$ and $\emptyset$. Before we prove the second requirments, $f(A) = f(V - A)$ is trivial either. Also, we have $max(f(A), f(B)) \ge f(A \cup B)$. Because if we think about $i \in A \cup B, j \not\in A \cup B$ then it should be one of “$i \in A, j \not\in A$ or $i \in B, j \not\in B$”.

Now, we can make 4 property of $f$ from the fact above.

$f(A)$ $\le$ $\max(f(A - B), f(A \cap B))$
$f(A)$ $=$ $f(V - A)$ $\le$ $\max(f(B - A),$ $f(V - (A \cup B)))$ $=$ $\max(f(B - A),$ $f(A \cup B))$
$f(B)$ $\le$ $\max(f(B - A), f(A \cap B))$
$f(B)$ $=$ $f(V - B)$ $\le$ $\max(f(A - B),$ $f(V - (A \cup B)))$ $=$ $\max(f(A - B),$ $f(A \cup B))$

Notice that $(A - B)$ $\cup$ $(A \cap B)$ $=$ $A$, $(V - (A \cup B))$ $\cup$ $(B - A)$ $=$ $V$ $-$ $A$, $(B - A)$ $\cup$ $(A \cap B)$ $=$ $B$ and $(V- (A \cup B))$ $\cup$ $(A - B)$ $=$ $V$ $-$ $B$.

This implies 4 inequalities.

$f(A) + f(B)$ $\le$ $\max(f(A - B), f(A \cap B))$ $+$ $\max(f(B - A), f(A \cap B))$
$f(A) + f(B)$ $\le$ $\max(f(A - B), f(A \cap B))$ $+$ $\max(f(A - B), f(A \cup B))$
$f(A) + f(B)$ $\le$ $\max(f(B - A), f(A \cup B))$ $+$ $\max(f(B - A), f(A \cap B))$
$f(A) + f(B)$ $\le$ $\max(f(B - A), f(A \cup B))$ $+$ $\max(f(A - B), f(A \cup B))$

Then, we can make possible inequality for weakly supermodular in any case.

$f(A) + f(B)$ $\le$ $\max(f(A - B), f(A \cap B))$ $+$ $\max(f(B - A), f(A \cap B))$ $=$ $f(A - B)$ $+$ $f(B - A)$ if $f(A - B), f(B - A)$ $\ge$ $f(A \cap B)$
$f(A) + f(B)$ $\le$ $\max(f(A - B), f(A \cap B))$ $+$ $\max(f(A - B), f(A \cup B))$ $=$ $f(A \cap B)$ $+$ $f(A \cup B)$ if $f(A \cap B), f(A \cup B)$ $\ge$ $f(A - B)$
$f(A) + f(B)$ $\le$ $\max(f(B - A), f(A \cup B))$ $+$ $\max(f(B - A), f(A \cap B))$ $=$ $f(A \cap B)$ $+$ $f(A \cup B)$ if $f(A \cap B), f(A \cup B)$ $\ge$ $f(B - A)$
$f(A) + f(B)$ $\le$ $\max(f(B - A), f(A \cup B))$ $+$ $\max(f(A - B), f(A \cup B))$ $=$ $f(A - B)$ $+$ $f(B - A)$ if $f(A - B), f(B - A)$ $\ge$ $f(A \cup B)$

Notice that if all requirements is false then all following should be true.

$\min(f(A - B), f(B - A))$ $<$ $f(A \cap B)$
$\min(f(A \cap B), f(A \cup B))$ $<$ $f(A - B)$
$\min(f(A \cap B), f(A \cup B))$ $<$ $f(B - A)$
$\min(f(A - B), f(B - A))$ $<$ $f(A \cup B)$

This leads to a contradiction, as shown by the following reasoning.

$\min(f(A - B), f(B - A))$ $<$ $\min(f(A \cap B), f(A \cup B))$ from 1, 4
$\min(f(A \cap B), f(A \cup B))$ $<$ $\min(f(A - B), f(B - A))$ from 2, 3
$\min(f(A \cap B), f(A \cup B))$ $<$ $\min(f(A - B), f(B - A))$ $<$ $\min(f(A \cap B), f(A \cup B))$ from above two.
As a result, $\min(f(A \cap B), f(A \cup B))$ $<$ $\min(f(A \cap B), f(A \cup B))$ and it can’t be true. Therefore, $f$ is a weakly supermodular.

There is a key property of weakly supermodular functions $f$: if we solve “Minimize $\sum\limits_{e \in E} c_e x_e$ such that $\sum\limits_{e \in \delta(S)} x_e \ge f(S)$ $\forall S \subset V$, $0 \le x_e \le 1$”, then there exists an edge $e \in E$ with $x_e \ge \frac{1}{2}$. The proof is given at the end of this post.

From the fact above, we can construct an algorithm.

$F \leftarrow \emptyset$
$i \leftarrow 1$
$\operatorname{while}$ $F$ is not a feasible solution $\textbf{do}$

Solve "Minimize $\sum\limits_{e \in E - F} c_e x_e$ such that $\sum\limits_{e \in \delta(S), e \in E - F} x_e \ge f_i(S) = f(S) - |\delta(S) \cap F|$ $\forall S \subset V$, $0 \le x_e \le 1$"
$F_i \leftarrow \{ e \in E - F \vert x_e \ge \frac{1}{2} \}$
$F \leftarrow F \cup F_i$
$i \leftarrow i + 1$

$\textbf{return} \text{ } F$

This is called $\operatorname{iterative rounding}$: it uses LP relaxation to extend the solution and repeats the process.

If the algorithm above terminates, solution should be feasible. Now, we will show that solution will be in $2\operatorname{OPT}$ and it terminates.

First of all, we will show “If we define $z(e) \ge 0$ for all $e \in E$ and define $z(E) = \sum\limits_{e \in E}z(e)$ then $z(\delta(A)) + z(\delta(B))$ $\ge$ $z(\delta(A \cup B)) + z(\delta(A \cap B))$ and $z(\delta(A)) + z(\delta(B))$ $\ge$ $z(\delta(A - B)) + z(\delta(B - A))$ for any $A, B \subset V$”.

Proof is like follow. If you think about the category of edges in $\delta(A)$, it will be one of follows.

$i \in A - B$, $j \in V - (A \cup B)$
$i \in A \cap B$, $j \in V - (A \cup B)$
$i \in A - B$, $j \in B - A$
$i \in A \cap B$, $j \in B - A$

It’s the same for the B either. Therefore, $z(\delta(A)) + z(\delta(B))$ will be sum of $z(e)$ in following 8 categories.

$i \in A - B$, $j \in V - (A \cup B)$
$i \in A \cap B$, $j \in V - (A \cup B)$
$i \in A - B$, $j \in B - A$
$i \in A \cap B$, $j \in B - A$
$i \in B - A$, $j \in V - (A \cup B)$
$i \in A \cap B$, $j \in V - (A \cup B)$
$i \in B - A$, $j \in A - B$
$i \in A \cap B$, $j \in A - B$

If you think about the category of edges in $\delta(A \cup B)$, it will be one of follows.

$i \in A - B$, $j \in V - (A \cup B)$
$i \in A \cap B$, $j \in V - (A \cup B)$
$i \in B - A$, $j \in V - (A \cup B)$

If you think about the category of edges in $\delta(A \cap B)$, it will be one of follows.

$i \in A \cap B$, $j \in V - (A \cup B)$
$i \in A \cap B$, $j \in B - A$
$i \in A \cap B$, $j \in A - B$

Therefore, $z(\delta(A \cup B)) + z(\delta(A \cap B))$ will be sum of $z(e)$ in following 6 categories.

$i \in A - B$, $j \in V - (A \cup B)$
$i \in A \cap B$, $j \in V - (A \cup B)$
$i \in B - A$, $j \in V - (A \cup B)$
$i \in A \cap B$, $j \in V - (A \cup B)$
$i \in A \cap B$, $j \in B - A$
$i \in A \cap B$, $j \in A - B$

Now, we can do a mapping from this categories of $z(\delta(A \cup B)) + z(\delta(A \cap B))$ to one of 8 categories of $z(\delta(A)) + z(\delta(B))$. $1 \rightarrow 1$, $2 \rightarrow 2$, $3 \rightarrow 5$, $4 \rightarrow 6$, $5 \rightarrow 4$, $6 \rightarrow 8.$ Now we have category 3, 7 lefts. As a result, $z(\delta(A)) + z(\delta(B))$ $\ge$ $z(\delta(A \cup B)) + z(\delta(A \cap B))$.

Like above, we can do the same thing for $z(\delta(A)) + z(\delta(B))$ $\ge$ $z(\delta(A - B)) + z(\delta(B - A))$.

If you think about the category of edges in $\delta(A - B)$, it will be one of follows.

$i \in A - B$, $j \in V - (A \cup B)$
$i \in A - B$, $j \in A \cap B$
$i \in A - B$, $j \in B - A$

If you think about the category of edges in $\delta(B - A)$, it will be one of follows.

$i \in B - A$, $j \in V - (A \cup B)$
$i \in B - A$, $j \in A \cap B$
$i \in B - A$, $j \in A - B$

Therefore, $z(\delta(A - B)) + z(\delta(B - A))$ will be sum of $z(e)$ in following 6 categories.

$i \in A - B$, $j \in V - (A \cup B)$
$i \in A - B$, $j \in A \cap B$ $\leftrightarrow$ $i \in A \cap B$, $j \in A - B$
$i \in A - B$, $j \in B - A$
$i \in B - A$, $j \in V - (A \cup B)$
$i \in B - A$, $j \in A \cap B$ $\leftrightarrow$ $i \in A \cap B$, $j \in B - A$
$i \in B - A$, $j \in A - B$

We can map $1 \rightarrow 1$, $2 \rightarrow 8$, $3 \rightarrow 3$, $4 \rightarrow 5$, $5 \rightarrow 4$, $6 \rightarrow 7$. Now we have category 2, 6 lefts. As a result, $z(\delta(A)) + z(\delta(B))$ $\ge$ $z(\delta(A - B)) + z(\delta(B - A))$.

As a summary, both followings are true.

$z(\delta(A)) + z(\delta(B))$ $\ge$ $z(\delta(A \cup B)) + z(\delta(A \cap B))$
$z(\delta(A)) + z(\delta(B))$ $\ge$ $z(\delta(A - B)) + z(\delta(B - A))$

Now, let $z_F(e) = 1$ if $e \in F$ and $z_F(e) = 0$ otherwise.

Then, $f_i(S) = f(S) - |\delta(S) \cap F| = f(S) - z_F(\delta(S))$. As a result $f_i(S)$ should fulfill one of follows.

$f_i(A)$ $+$ $f_i(B)$ $=$ $f(A)$ $+$ $f(B)$ $-$ $z_F(\delta(A))$ $-$ $z_F(\delta(B))$ $\le$ $f(A \cup B)$ $+$ $f(A \cap B)$ $-$ $z_F(\delta(A \cup B))$ $-$ $z_F(\delta(A \cap B))$ $=$ $f_i(A \cup B)$ $+$ $f_i(A \cap B)$.
$f_i(A)$ $+$ $f_i(B)$ $=$ $f(A)$ $+$ $f(B)$ $-$ $z_F(\delta(A))$ $-$ $z_F(\delta(B))$ $\le$ $f(A - B)$ $+$ $f(B - A)$ $-$ $z_F(\delta(A - B))$ $-$ $z_F(\delta(B - A))$ $=$ $f_i(A - B)$ $+$ $f_i(B - A)$.

Now, we showed that $f_i$ is a weakly supermodular.

Therefore, we can found at least one edge such that $x_e \ge \frac{1}{2}$ for any $f_i$. Now if we can show that “Minimize $\sum\limits_{e \in E - F} c_e x_e$ such that $\sum\limits_{e \in \delta(S), e \in E - F} x_e \ge f_i(S) = f(S) - |\delta(S) \cap F|$ $\forall S \subset V$, $0 \le x_e \le 1$” can be solved in polynomial time, it will the end of the proof for polynomial execution time for the algorithm. Notice that we can do this at most $O(\left\vert E \right\vert)$.

We still can use network flow algorithm to solve this. Therefore, we will make a seperation orcale like below.

Make a graph that consists of $G = (V,E)$ and set capacity of $E - F$ as $x_e$ and capacity of $F$ as 1.
Solve the network flow problem between all pair $i$ and $j$ such that $i \neq j$ and $i,j \in V$.
If there is a flow such that the value of flow $f_{ij}$ is less than $r_{ij}$ then it’s an infeasible solution otherwise it is feasible.

Notice that if it is feasible then it means $\sum\limits_{e \in \delta(S)} f_e + |\delta(S) \cap F| \ge r_{ij}$ which $\delta(S)$ denotes the set of edges between $S$ and $V - S$ in $E - F$. As a result, $\sum\limits_{e \in \delta(S)} f_e \ge r_{ij} - |\delta(S) \cap F|$. If there is some $i, j$ such that flow between $i$ and $j$ is less than $r_{ij}$ then there should be $S$ such that $\sum\limits_{e \in \delta(S)} f_e + |\delta(S) \cap F|< r_{ij}$. As a result, we can use this as a seperation orcale.

The only remaining thing to show is that the solution is within $2\operatorname{OPT}$. To show this, we will prove generalized version of the claim. The claim is “For any weakly supermodular function $f$, let’s define $x^i$ as the solution of LP in $i$th iteration. If we can solve iterative rounding algorithm above in $k$ iteration then solution of iterative rounding $\operatorname{ANS}$ $=$ $\sum\limits_{e \in F} c_e$ is in $2\sum\limits_{e \in E} c_e x_e^1$”. Notice that this implies $\operatorname{ANS}$ $=$ $\sum\limits_{e \in F} c_e$ $\le$ $2\sum\limits_{e \in E} c_e x_e^1$ $\le$ $2\operatorname{OPT}$.

We will show this in the inductive method.

If $k = 1$, we will solve “Minimize $\sum\limits_{e \in E} c_e x_e$ such that $\sum\limits_{e \in \delta(S), e \in E} x_e \ge f(S)$ $\forall S \subset V$, $0 \le x_e \le 1$” once and that’s all. From the above, we will select $\{x_e : x_e \ge \frac{1}{2}\}$. As a result, $\sum\limits_{e \in F_1} c_e$ $\le$ $2\sum\limits_{e \in F_1} c_e x_e^1$.

If $k \ge 2$, we have three facts follow. First, $\sum\limits_{e \in F_1} c_e$ $\le$ $2\sum\limits_{e \in F_1} c_e x_e^1$ is true because we selected $x_e^1 \ge \frac{1}{2}$ in $x_e^1$.

Also, if we consider $\{x_e^1 | e \in E - F_1\}$ $=$ $\Lambda$ then $\Lambda$ is a feasible solution of LP in the second iteration either. The reason is like follow. Second constraint is trivial to be hold because $0 \le x_e^1 \le 1$. First constraint holds either because of follows. $\sum\limits_{e \in \delta(S), e \in E - F_1} x_e^1$ $=$ $\sum\limits_{e \in \delta(S), e \in E} x_e^1 - \sum\limits_{e \in \delta(S), e \in F_1} x_e^1$ $\ge$ $f_1(S) - |\delta(S) \cap F_1|$ $=$ $f_2(S)$. Therefore, $\Lambda$ is a feasible solution. As a result, $\sum\limits_{e \in E - F_1} c_e x_e^1$ $\ge$ $\sum\limits_{e \in E - F_1} c_e x_e^2$.

For the last, we can use iterative rounding for $E - F_1$ and $f_2(S)$ because it will terminted in $k - 1$ iterations. Notice that we’ve proved that $f_2$ is a weakly supermodular. As a result, $\sum\limits_{e \in F - F_1} c_e$ $\le$ $2\sum\limits_{e \in E - F_1} c_e x_e^2$.

In a summary, we have three facts.

$\sum\limits_{e \in F_1} c_e$ $\le$ $2\sum\limits_{e \in F_1} c_e x_e^1$
$\sum\limits_{e \in E - F_1} c_e x_e^2$ $\le$ $\sum\limits_{e \in E - F_1} c_e x_e^1$
$\sum\limits_{e \in F - F_1} c_e$ $\le$ $2\sum\limits_{e \in E - F_1} c_e x_e^2$.

If we combine three facts above, $\sum\limits_{e \in F} c_e$ $=$ $\sum\limits_{e \in F - F_1} c_e + \sum\limits_{e \in F_1} c_e$ $\le$ $2\sum\limits_{e \in E - F_1} c_e x_e^2 + 2\sum\limits_{e \in F_1} c_e x_e^1$ $\le$ $2\sum\limits_{e \in E - F_1} c_e x_e^1 + 2\sum\limits_{e \in F_1} c_e x_e^1$ $=$ $2\sum\limits_{e \in E} c_e x_e^1$.

Now proof stops here for survivable network design problem.

However, we need to show one following fact. There exists an edge $e \in E$ such that $x_e \ge \frac{1}{2}$ if we solve linear problem “Minimize $\sum\limits_{e \in E} c_e x_e$ such that $\sum\limits_{e \in \delta(S)} x_e \ge f(S)$ $\forall S \subset V$, $0 \le x_e \le 1$” for any weakly supermodular $f$.

To show this proof, we need some definitions to make a proof.

$\chi_E$ is a vector such that $(\chi_E)_e$ $=$ $\cases{ 1, e \in E, x_e > 0\cr 0, \text{otherwise}}$
$A$ and $B$ are intersecting if all of $A \cap B$, $A - B$ and $B - A$ are not empty.
$A$ is tight if $\sum\limits_{e \in \delta(A)} x_e = f(A)$ for $A \in V$.
A collection of sets $\mathcal{L}$ is $\operatorname{laminor}$ if no pair of sets in $\mathcal{L}$ is intersecting.
$\operatorname{Span}(\mathcal{L})$ $=$ $\operatorname{Span}{\chi_{\delta(S)} \mid S \in \mathcal{L}}$

We need several lemmas.

If $A$ and $B$ are tight and intersecting, at least one of the following is true.

$A \cap B$, $A \cup B$ are both tight and $\chi_{\delta(A \cap B)} + \chi_{\delta(A \cup B)}$ $=$ $\chi_{\delta(A)} + \chi_{\delta(B)}$
$A - B$, $B - A$ are both tight and $\chi_{\delta(A - B)} + \chi_{\delta(B - A)}$ $=$ $\chi_{\delta(A)} + \chi_{\delta(B)}$

Proof is like follow. one of $f(A) + f(B)$ $\le$ $f(A \cap B) + f(A \cup B)$ or $f(A) + f(B)$ $\le$ $f(A - B) + f(B - A)$ is true because $f$ is a weakly supermodular. Then, there are two cases. If we think about the first case, we can do a reasoning follow. $\sum\limits_{e \in \delta(A \cap B)} x_e$ $+$ $\sum\limits_{e \in \delta(A \cup B)} x_e$ $\ge$ $f(A \cap B) + f(A \cup B)$ because of constraints of linear problem. $f(A \cap B) + f(A \cup B)$ $\ge$ $f(A) + f(B)$ because $f$ is a weakly super modular. $f(A) + f(B)$ $=$ $\sum\limits_{e \in \delta(A)} x_e$ $+$ $\sum\limits_{e \in \delta(B)} x_e$ becacuse $A$ and $B$ is tight. As a result, $\sum\limits_{e \in \delta(A \cap B)} x_e$ $+$ $\sum\limits_{e \in \delta(A \cup B)} x_e$ $\ge$ $\sum\limits_{e \in \delta(A)} x_e$ $+$ $\sum\limits_{e \in \delta(B)} x_e$.

With this fact, $\sum\limits_{e \in \delta(A \cap B)} x_e$ $+$ $\sum\limits_{e \in \delta(A \cup B)} x_e$ $\ge$ $\sum\limits_{e \in \delta(A)} x_e$ $+$ $\sum\limits_{e \in \delta(B)} x_e$ $\ge$ $\sum\limits_{e \in \delta(A \cap B)} x_e$ $+$ $\sum\limits_{e \in \delta(A \cup B)} x_e$ if we use the fact follow “If we select $z(e) \ge 0$ for all $e \in E$ and define $z(E) = \sum\limits_{e \in E}z(e)$ then $z(\delta(A)) + z(\delta(B))$ $\ge$ $z(\delta(A \cup B)) + z(\delta(A \cap B))$ and $z(\delta(A)) + z(\delta(B))$ $\ge$ $z(\delta(A - B)) + z(\delta(B - A))$ for any $A, B \subset V$”.

As a result, $\sum\limits_{e \in \delta(A \cap B)} x_e$ $+$ $\sum\limits_{e \in \delta(A \cup B)} x_e$ $=$ $f(A \cap B) + f(A \cup B)$ $=$ $f(A) + f(B)$ $=$ $\sum\limits_{e \in \delta(A)} x_e$ $+$ $\sum\limits_{e \in \delta(B)} x_e$ $=$ $\sum\limits_{e \in \delta(A \cap B)} x_e$ $+$ $\sum\limits_{e \in \delta(A \cup B)} x_e$. Which means that both $A \cap B$, $A \cup B$ are tight. More over, if we recap the process of prooving the statement of $z$, there were 8 categories of edges and 2 are lefts in each cases.

$i \in A - B$, $j \in V - (A \cup B)$
$i \in A \cap B$, $j \in V - (A \cup B)$
$i \in A - B$, $j \in B - A$
$i \in A \cap B$, $j \in B - A$
$i \in B - A$, $j \in V - (A \cup B)$
$i \in A \cap B$, $j \in V - (A \cup B)$
$i \in B - A$, $j \in A - B$
$i \in A \cap B$, $j \in A - B$

Now we have category 2, 6 lefts for $\delta(A - B)$ and $\delta(B - A)$. Similarly we have category 3, 7 lefts for $\delta(A \cup B)$ and $\delta(A \cap B)$.

However, $x_e$ for edges in category 2, 6 should be $0$ because $\sum\limits_{e \in \delta(A \cap B)} x_e$ $+$ $\sum\limits_{e \in \delta(A \cup B)} x_e$ $=$ $\sum\limits_{e \in \delta(A)} x_e$ $+$ $\sum\limits_{e \in \delta(B)} x_e$ and $0 \le x_e \le 1$. Then, we can know that $\delta(A \cap B)$, $\delta(A \cup B)$ and $\delta(A)$, $\delta(B)$ should have the same set of edges. As a result, $\chi_{\delta(A \cap B)} + \chi_{\delta(A \cup B)}$ $=$ $\chi_{\delta(A)} + \chi_{\delta(B)}$.

Simillarly, both $A - B$, $B - A$ are tight and $\chi_{\delta(A - B)} + \chi_{\delta(B - A)}$ $=$ $\chi_A + \chi_B$ should be hold in the second case.

Now, we will claim below with the lemma above. Then, there is $\mathcal{L} \subset 2^{V}$ which satisfies 4 things.

$S$ is tight for all $S \in \mathcal{L}$
$\{\chi_{\delta(S)}\}_{S \in \mathcal{L}}$ are linear independent.
$\left\vert \mathcal{L} \right\vert$ $=$ $\left\vert E \right\vert$
$\mathcal{L}$ is $\operatorname{laminor}$.

Proof is like follow. Let $\mathcal{T} \subset 2^{V}$ be the family of all tight sets and $\mathcal{L}$ be a maximal laminar subfamily of $\mathcal{T}$ (i.e., $\mathcal{L}$ ceases to be laminar if any additional set from $\mathcal{T}$ is added).

First, we will claim $\operatorname{Span}(\mathcal{T})$ $\subset$ $\operatorname{Span}(\mathcal{L})$ to show $\operatorname{Span}(\mathcal{T})$ $=$ $\operatorname{Span}(\mathcal{L})$. Notice that $\operatorname{Span}(\mathcal{L})$ $\subset$ $\operatorname{Span}(\mathcal{T})$ is trivial because $\mathcal{L} \subset \mathcal{T}$.

Let’s assume not then there are some $S$ $\in$ $\mathcal{T}$ such that $\chi_{\delta(S)}$ $\not\in$ $\operatorname{Span}(\mathcal{L})$. Between possible $S$s, let’s assume that we’ve choose $S$ such that $S$ has the fewest intersecting sets in $\mathcal{L}$. However, $S$ should intersect with at least one set in $\mathcal{L}$. The reason is that we can add $S$ to $\mathcal{L}$ because it doesn’t change $\mathcal{L}$ to be not $\operatorname{laminor}$ if it don’t intersect. However, it’s contradiction to “$\mathcal{L}$ is maximal $\operatorname{laminor}$”.

Now, we can find $T \in \mathcal{L}$ such that $T$ is intersecting with $S$. Then one of two need to be true because both $S$, $T$ are tight because $T \in \mathcal{L} \subset \mathcal{T}$ and $S \in \mathcal{T}$.

$S \cap T$, $S \cup T$ are both tight and $\chi_{\delta(S \cap T)} + \chi_{\delta(S \cup T)}$ $=$ $\chi_{\delta(S)} + \chi_{\delta(T)}$
$S - T$, $T - S$ are both tight and $\chi_{\delta(S - T)} + \chi_{\delta(T - S)}$ $=$ $\chi_{\delta(S)} + \chi_{\delta(T)}$

Let’s assume that it’s the case 1. Then both $\chi_{\delta(S \cap T)}$, $\chi_{\delta(S \cup T)}$ can’t be in $\operatorname{Span}(\mathcal{L})$ at the same time.

Proof is like follow. $\chi_{\delta(S)}$ $=$ $\chi_{\delta(S \cap T)}$ + $\chi_{\delta(S \cup T)}$ - $\chi_{\delta(T)}$ and $\chi_{\delta(S)}$ should be in $\operatorname{Span}(\mathcal{L})$ if $\chi_{\delta(S \cup T)}$, $\chi_{\delta(S \cap T)}$ are in $\operatorname{Span}(\mathcal{L})$ at the same time. It’s the same of case 2 because $\chi_{\delta(S)}$ $=$ $\chi_{\delta(S - T)}$ + $\chi_{\delta(T)}$ - $\chi_{\delta(T - S)}$.

Now, let’s think about $X$ such that $\chi_{\delta(X)} \not\in \operatorname{Span}(\mathcal{L})$ and $X \in \{S \cap T, S \cup T\}$ in the first case or $\{S - T, T - S\}$ in the second case. Then, $S$ and $Y$ are intersecting for any $Y \in \mathcal{L}$ such that $Y$ is intersecting with $X$.

Proof is like follow. Notice that $Y$ should be one of three followings because $Y \in \mathcal{L}$, $T \in \mathcal{L}$.

$Y \cap T = \emptyset$
$T - Y = \emptyset$
$Y - T = \emptyset$

Notice that all of followings are true.

$X \cap Y \neq \emptyset$
$X - Y \neq \emptyset$
$Y - X \neq \emptyset$
$S \cap T \neq \emptyset$
$S - T \neq \emptyset$
$T - S \neq \emptyset$

If $X = S \cap T$, $Y$ should fulfill one of three followings.

$Y \cap T = \emptyset$
$Y$ can’t intersect with $X$ because $Y \cap X$ $\subseteq$ $Y \cap T$ $=$ $\emptyset$.
Therefore, such $Y$ doesn’t exist.
$T - Y = \emptyset$
$Y$ can’t intersect with $X$ because $X - Y$ $\subseteq$ $T - Y$ $=$ $\emptyset$.
Therefore, such $Y$ doesn’t exist.
$Y - T = \emptyset$
$\emptyset$ $\neq$ $X \cap Y$ $\subseteq$ $S \cap Y$.
$\emptyset$ $\neq$ $X - Y$ $\subseteq$ $S - Y$.
$\emptyset$ $\neq$ $Y - X$ $=$ $Y - (S \cap T)$ $=$ $(Y - S)$ $\cup$ $(Y - T)$ $=$ $Y - S$.
As a result, $S$ intersects with $Y$.

If $X = S \cup T$, $Y$ should fulfill one of three followings.

$Y \cap T = \emptyset$
$\emptyset$ $\neq$ $X \cap Y$ $=$ $(S \cup T) \cap Y$ $=$ $(S \cap Y) \cup (T \cap Y)$ $=$ $S \cap Y$.
$\emptyset$ $\neq$ $S \cap T$ $=$ $(S \cap T) - (S \cap (T \cap Y))$ $=$ $(S \cap T) - ((S \cap T) \cap Y)$ $=$ $(S \cap T) - Y$ $\subseteq$ $((S \cap T) - Y) \cup ((S - T) - Y)$ $=$ $S - Y$.
$\emptyset$ $\neq$ $Y - X$ $\subseteq$ $Y - S$.
As a result, $S$ intersects with $Y$.
$T - Y = \emptyset$
$\emptyset$ $\neq$ $S \cap T$ $=$ $S \cap ((T \cap Y) \cup (T - Y))$ $=$ $S \cap (T \cap Y)$ $=$ $S \cap T \cap Y$ $=$ $(S \cap Y) \cap T$ $\subseteq$ $S \cap Y$.
$\emptyset$ $\neq$ $X - Y$ $=$ $(S \cup T) - Y$ $=$ $(S - Y) \cup (T - Y)$ $=$ $S - Y$.
$\emptyset$ $\neq$ $Y - X$ $\subseteq$ $Y - S$.
As a result, $S$ intersects with $Y$.
$Y - T = \emptyset$
$Y$ can’t intersect with $X$ because $Y - X$ $\subseteq$ $Y - T$ $=$ $\emptyset$.
Therefore, such $Y$ doesn’t exist.

If $X = S - T$, $Y$ should fulfill one of three followings.

$Y \cap T = \emptyset$
$\emptyset$ $\neq$ $X \cap Y$ $=$ $(S - T) \cap Y$ $\subseteq$ $S \cap Y$.
$\emptyset$ $\neq$ $X - Y$ $\subseteq$ $S - Y$.
$\emptyset$ $\neq$ $Y - X$ $=$ $Y - (S - T)$ $=$ $Y - (Y \cap (S - T))$ $=$ $Y - ((Y \cap S) - (Y \cap T))$ $=$ $Y - (Y \cap S)$ $=$ $Y - S$.
As a result, $S$ intersects with $Y$.
$T - Y = \emptyset$
$\emptyset$ $\neq$ $X \cap Y$ $=$ $(S - T) \cap Y$ $=$ $(S \cap Y) - (T \cap Y)$ $\subseteq$ $S \cap Y$.
$\emptyset$ $\neq$ $X - Y$ $\subseteq$ $S - Y$.
$\emptyset$ $\neq$ $T - S$ $\subseteq$ $(Y \cup T) - S$ $=$ $(Y \cup (T - Y)) - S$ $=$ $(Y - S) \cup ((T - Y) - S)$ $=$ $Y - S$.
As a result, $S$ intersects with $Y$.
$Y - T = \emptyset$
$Y$ can’t intersect with $X$ because $X \cap Y$ $=$ $(S - T) \cap Y$ $=$ $(S \cap Y) - (T \cap Y)$ $=$ $(S \cap Y) - ((T \cap Y) \cup (Y - T))$ $\subseteq$ $((S \cap Y) \cup (Y - S)) - ((T \cap Y) \cup (Y - T))$ $=$ $Y - Y$ $=$ $\emptyset$.
Therefore, such $Y$ doesn’t exist.

If $X = T - S$, $Y$ should fulfill one of three followings.

$Y \cap T = \emptyset$
$Y$ can’t intersect with $X$ because $X \cap Y$ $=$ $(T - S) \cap Y$ $\subseteq$ $T \cap Y$ $=$ $\emptyset$.
Therefore, such $Y$ doesn’t exist.
$T - Y = \emptyset$
$Y$ can’t intersect with $X$ because $X - Y$ $=$ $(T - S) - Y$ $\subseteq$ $T - Y$ $=$ $\emptyset$.
Therefore, such $Y$ doesn’t exist.
$Y - T = \emptyset$
$\emptyset$ $\neq$ $Y - X$ $=$ $Y - (T - S)$ $=$ $Y - ((T \cup (Y - T)) - S)$ $=$ $Y - ((Y \cup T) - S)$ $=$ $Y - ((Y \cup (T - Y)) - S)$ $\subseteq$ $Y - (Y - S)$ $=$ $S \cap Y$.
$\emptyset$ $\neq$ $S - T$ $=$ $S - (T \cup (Y - T))$ $=$ $S - (Y \cup T)$ $=$ $S - (Y \cup (T - Y))$ $\subseteq$ $S - Y$.
$\emptyset$ $\neq$ $X \cap Y$ $=$ $(T - S) \cap Y$ $=$ $(T - (S \cap T)) \cap Y$ $=$ $(T \cap Y) - ((S \cap T) \cap Y)$ $=$ $(T \cap Y) - (S \cap (T \cap Y))$ $=$ $(T \cap Y) - S$ $=$ $((T \cap Y) \cup (Y - T)) - S$ $=$ $Y - S$.
As a result, $S$ intersects with $Y$.

As a result, $S$ and $Y$ are intersecting for any $Y \in \mathcal{L}$ such that $Y$ is intersecting with $X$.

Now, let’s think about $X$. Then, $X$ should have strictly fewer intersecting sets with $\mathcal{L}$ than $S$. The reason is like follow. If $X$ is intersecting with $Y \in \mathcal{L}$ then, $S$ does so either. However, there is at least one set such that intersects with $S$ but not with $X$ which is $T$. Notice that $X \in \{S \cap T, S \cup T, S - T, T - S\}$ and $(S \cap T) - T = \emptyset$, $T - (S \cup T) = \emptyset$, $(S - T) \cap T = \emptyset$, $(T - S) - T= \emptyset$. However, this is contradiction that we’ve choosed $S$ such that has $S$ has the fewest intersecting sets in $\mathcal{L}$.

Therefore, such an $S$ can’t exists and $\operatorname{Span}(\mathcal{T})$ $=$ $\operatorname{Span}(\mathcal{L})$ is true. Now, we’ve showend that there is at least one of a maximal $\operatorname{laminor}$ subfamily of $\mathcal{T}$ namely $\mathcal{L}$ such that fulfills following two.

$S$ is tight for all $S \in \mathcal{L}$
$\mathcal{L}$ is $\operatorname{laminor}$.

Now, we can find some set $S \in \mathcal{T}$ which is lineary dependent from other vectors. Then, we can just remove it without losing property above. We continue until all vectors are linearly independent; call the result $\mathcal{L}^\star$. Then $\mathcal{L}^\star$ contains $\left\vert E \right\vert$ linearly independent vectors, and $\operatorname{Span}(\mathcal{L}^\star)$ remains equal to $\operatorname{Span}(\mathcal{T})$ since we removed only linearly dependent vectors. Notice that each vector has $\left\vert E \right\vert$ elements inside. Therefore, $\mathcal{L}^\star$ fulfills every property below.

$S$ is tight for all $S \in \mathcal{L}^\star$
$\{\chi_{\delta(S)}\}_{S \in \mathcal{L}^\star}$ are linear independent.
$\left\vert \mathcal{L}^\star \right\vert$ $=$ $\left\vert E \right\vert$
$\mathcal{L}^\star$ is $\operatorname{laminar}$.

Now, we will show the following is true.

There exists an edge $e \in E$ such that $x_e \ge \frac{1}{2}$ if we solve linear problem “Minimize $\sum\limits_{e \in E} c_e x_e$ such that $\sum\limits_{e \in \delta(S)} x_e \ge f(S)$ $\forall S \subset V$, $0 \le x_e \le 1$” for any weakly supermodular $f$.

To show this, let’s think about such an $\mathcal{L}$ satisfies 4 properties from given LP and let’s assume that $0 < x_e < \frac{1}{2}$ for all $e \in E$. Now, let’s define set $A$ is bigger than $B$ when $B \subset A$. Then we can construct a forest since $\mathcal{L}$ is a $\operatorname{laminor}$. Notice that one of following should be true for $X, Y \in \mathcal{L}$.

$X \cap Y$ $=$ $\emptyset$
$X - Y$ $=$ $\emptyset$ $\leftrightarrow$ $X \subseteq Y$
$Y - X$ $=$ $\emptyset$ $\leftrightarrow$ $Y \subseteq X$

From the fact above, we will construct a forest like follow.

Select biggest sets in $\mathcal{L}$ and make them to the roots.
Select biggest sets in $S$ for any root $S$ and make them to child of $S$.
Keep do this recursively untill every set is in the forest.

Notice that $X$ is the child of $S$ if and only if there is no set $Y$ exists such that $Y$ is the child of $S$ but $X$ is child of $Y$ either. It means there is no double depth child relation.

With this $\mathcal{L}$, we can pass some costs to the sets. Let’s pass the costs like follow.

Pass $x_e$ to set $X$ if $u$ or $v$ is in $X$ and $X$ is the smallest set among such sets for any edge $e = (u,v)$.
Pass $1 - 2x_e$ to set $X$ if both $u$ and $v$ are in $X$ and $X$ is the smallest set among such sets for any edge $e = (u,v)$.

Then, select a root of forest $S$. With this $S$, let’s define child of $S$ as $C_1, C_2, \cdots, C_n$ and $C = \bigcup\limits_{k = 1}^{n} C_k$. Then, we can define 4 categories for edge $e \in (\delta(S) \cup \delta(C))$.

$E_{cc}$ is the set of edges $e \in E$ such that one end point of edge is in $C_i$ and other is in $C_j$ for $i \neq j$.
$E_{cp}$ is the set of edges $e \in E$ such that one end point of edge is in $C_i$ and other is in $S - C$.
$E_{co}$ is the set of edges $e \in E$ such that one end point of edge is in $C_i$ and other is in $V - S$.
$E_{po}$ is the set of edges $e \in E$ such that one end point of edge is in $S - C$ and other is in $V - S$.

If we count every cost gain for $S$ from each categories, it is like follow.

$1 - 2x_e$ from $E_{cc}$.
$1 - 2x_e + x_e = 1 - x_e$ from $E_{cp}$.
Nothing from $E_{co}$.
$x_e$ from $E_{po}$.

Then, the total costs $S$ gain is $\left\vert E_{cc} \right\vert$ $-$ $2x(E_{cc})$ $+$ $\left\vert E_{cp} \right\vert$ $-$ $x(E_{cp})$ $+$ $x(E_{po})$ $=$ $\left\vert E_{cc}\right\vert$ $+$ $\left\vert E_{cp} \right\vert$ $-$ $2x(E_{cc})$ $-$ $x(E_{cp})$ $+$ $x(E_{po})$.

Notice that $E_{cc} \cup E_{cp} \cup E_{po} \neq \emptyset$. Proof is like follow.

Let’s assume not then $E_{cc} = E_{cp} = E_{po} = \emptyset$. Which means $x(\delta(S))$ $=$ $x(E_{po} + E_{co})$ $=$ $x(E_{co})$ $=$ $x(E_{co} \cup E_{cc} \cup E_{cp})$ $=$ $x(\delta(C))$ $=$ $x(\delta(\bigcup\limits_{k = 1}^{n} C_k))$ $=$ $\sum\limits_{k = 1}^n x(\delta(C_k))$ because $C_i \cap C_j = \emptyset$. Notice that $C_i$ is the sibling of $C_j$ in the forest. However, $x(\delta(S))$ $=$ $\sum\limits_{k = 1}^n x(\delta(C_k))$ can’t be true because it’s a contradiction for the fact that $\chi_{\delta(S)}$, $\chi_{\delta(C_1)}$, $\cdots$, $\chi_{\delta(C_n)}$ are linear independent. Therefore, $\left\vert E_{cc} \right\vert$ $-$ $2x(E_{cc})$ $+$ $\left\vert E_{cp} \right\vert$ $-$ $x(E_{cp})$ $+$ $x(E_{po})$ $>$ $0$. Notice that every value is positive because we assumed $0 < x_e < \frac{1}{2}$.

Now, let’s think about the categories of edges for $E_{cc}, E_{cp}, E_{po}$. Then $x(\delta(S))$ $=$ $x(E_{po})$ $+$ $x(E_{co})$ and $x(\delta(C))$ $=$ $x(E_{cp})$ $+$ $2x(E_{cc})$ $+$ $x(E_{co})$. Reason is like follow.

For $\delta(S)$, all the edges should be one of $E_{co}$ or $E_{po}$ because one of end point should be in $V - S$.
For $\delta(C)$, there are three type of edges like just described. One for from $C_i$ to $V - S$. One for from $C_i$ to $S - C$. One for from $C_i$ to $C_j$ for $i \neq j$. However, $x(\delta(C))$ will count twice for “One for from $C_i$ to $C_j$ for $i \neq j$”.

As a result, $\left\vert E_{cc} \right\vert$ $+$ $\left\vert E_{cp} \right\vert$ $-$ $2x(E_{cc})$ $-$ $x(E_{cp})$ $+$ $x(E_{po})$ $=$ $\left\vert E_{cc} \right\vert$ $+$ $\left\vert E_{cp} \right\vert$ $+$ $x(E_{po})$ $+$ $x(E_{co})$ $-$ $(x(E_{cp}) + 2x(E_{cc}) + x(E_{co}))$ $=$ $\left\vert E_{cc} \right\vert$ $+$ $\left\vert E_{cp} \right\vert$ $+$ $x(\delta(S))$ $-$ $x(\delta(C))$. However, $\left\vert E_{cc} \right\vert$ $+$ $\left\vert E_{cp} \right\vert$ $+$ $x(\delta(S))$ $-$ $x(\delta(C))$ should be an integer because all of elements in the equation are intergers. Therefore, each $S$ should have at least 1 costs. Which means total cost of $\mathcal{L}$ $\ge$ $\left\vert E \right\vert$ since $\left\vert \mathcal{L} \right\vert$ $=$ $\left\vert E \right\vert$. However, total cost of $\mathcal{L}$ $<$ $\left\vert E \right\vert$ is true because of following reasons.

Each edge passes at most $x_e + x_e + (1 - 2x_e) = 1$ cost to sets. Therefore, total cost of $\mathcal{L} \le \left\vert E \right\vert$. However, there is at least one edge that outgoing of $S$. If there is no such an edge, $S$ should contain every vertices and it means $S = V$. However if so, $\delta(S) = \emptyset$ because there is no edge between $S$ and $S - V = V - V = \emptyset$. Which means $S$ can’t be in $\mathcal{L}$ because $\chi_{\delta(S)} = \vec{0}$ can’t be the vector in the lineary indepdendent set. As a result, total cost of $\mathcal{L} < \left\vert E \right\vert$.

Therefore, it’s a contradiction with the fact above. As a result, assumption that “$0 < x_e < \frac{1}{2}$ for all $e \in E$” is false. Therefore, there must exist at least one $x_e$ such that $x_e \ge \frac{1}{2}$ or $x_e = 0$. However, if we think about the LP with removing $x_e$s such that $x_e = 0$ then solution of problem should be the same with before. At the same time, there should be at least one $x_e$ such that $x_e \ge \frac{1}{2}$ or $x_e = 0$. However, that should be the case of $x_e \ge \frac{1}{2}$ because we just removed every $x_e = 0$. Therefore, claim holds.