In this problem, we consider an unweighted version of the minimum multicut problem from Section 8.3. We are given a graph $G=(V, E)$ and $k$ pairs of source-sink vertices, $s_i, t_i \in V$ for $i=1, \ldots, k$. We wish to find a subset of edges $F \subseteq E$ that minimizes $|F|$ such that for each $i=1, \ldots, k$, there is no $s_i-t_i$ path in $(V, E-F)$.
Consider the following vector program:
$$
\begin{array}{lrl}
\operatorname{minimize} & \sum_{(i, j) \in E}\left(1-v_i-v_j\right) & \\
\text { subject to } & \begin{array}{rll}
v_{s_i}-v_{\tau_i} & =0, & \\
v_j-v_j & =1, & \\
v_j & \in \Re^a, & \\
& \forall j \in V,
\end{array}, \\
& & \forall j \in V .
\end{array}
$$
Consider the demand graph $H=\left(V, E^{\prime}\right)$, where $E^{\prime}=\left\{\left(s_i, t_i\right): i=1, \ldots, k\right\}$. Let $\Delta$ be the maximum degree of a vertex in the demand graph. Suppose that that the optimal value of the vector programming relaxation is $\epsilon|E|$. Consider the following algorithm which is similar to the algorithm in Section 6.5 for coloring 3 -colorable graphs. We draw $\ell=\left\lceil\log _2(\Delta / t)\right\rceil$ random vectors $\tau_1, \ldots, \tau_t$. The $\ell$ random vectors define $2^t$ different regions into which the vectors $v_i$ can fall: one region for each distinct possibility of whether $r_j \cdot v_i \geq 0$ or $r_j \cdot v_i<0$ for all $j=1, \ldots, t$. Remove all edges ( $i, j$ ) from the graph such that $v_i$ and $v_j$ are in different regions. If for any $s_i-t_i$ pair, there still exists an $s_i-t_i$ path, remove all edges incident on $s_i$. We now analyze this algorithm.
(a) Prove that the vector program is a relaxation of the unweighted minimum multicut problem.
(b) For any $(i, j) \in E$, prove that the probability that $i$ and $j$ are in different regions is at most $t \cdot \sqrt{1-v_i-v_j}$.
(c) Prove that for any $i=1, \ldots, k$, the probability that we end up removing all the edges incident on $i$ is at most $\Delta 2^{-t}$.
(d) Show that the expected number of edges removed is at most $O(\sqrt{\epsilon} \log (\Delta / \epsilon))|E|$.
For the final item, it may be useful to use Jensen's inequality, which states that for any convex function $f$ (that is, $f^{\prime \prime}(x) \geq 0$ ) and any positive $p_i$,
$$
f\left(\frac{\sum_i p_i x_i}{\sum_i p_i}\right) \leq \frac{1}{\sum_i p_i} \sum_i p_i f\left(x_i\right)
$$
The arithmetic-geometric mean inequality given in Fact 5.8 is a special case of Jensen's inequality with $f(x)=-\log x$ and all the $p_i=1$.