CS application: Large cuts

For graph $G$, we say that a set of vertices is non-trivial if it is non-empty and not equal to $V(G)$. A cut is a non-trivial set $S\subseteq V(G)$, and the size of this cut is the number of edges with exactly one endpoint in $S$. Denote by $\delta_G(S)$ the set of edges with exactly one endpoint in $S$ (these are the edges in the cut $S$).

Theorem 42

For every graph $G$, there exists a cut of size at least half of the number of edges of $G$.

Denote by $m$ and $n$ the number of edges and vertices of $G$ respectively. For simplicity, $V(G) = [n]$ (so that we have vertices as numbers). To prove this theorem, we present a randomized algorithm that finds such a large cut. We start from $S = \emptyset$. For each vertex $i \in [n]$, toss an unbiased coin and if the result is head, we put $i$ in set $S$; otherwise, $i$ is not in $S$.

This algorithm defines a probability space which is the same as tossing our coin $n$ times, i.e., $\Omega = \{0,1\}^n$ and uniform distribution. Each atomic event corresponds to a cut $S \subseteq [n]$ (i.e., $S$ is the set of indices $i$ where the $i$-th toss is head). Let $X$ be the number of edges in $\delta_G(S)$ (this is a random variable since it is a function of $S \in \Omega$). So we can write $X = \sum_{e \in E(G)} X_e$ where $X_e$ indicates whether an edge $e$ is in $\delta_G(S)$.

We argue that ${\mathbb E}[X_e] = 1/2$. Let $e = \{i,j\}$.

${\mathbb P}[\{i,j\} \in \delta_G(S)] = {\mathbb P}[i \in S, j \not\in S] + {\mathbb P}[i \not \in S, j \in S] = (1/2)(1/2) + (1/2)(1/2) = 1/2$

Therefore, we have ${\mathbb E}[X] = m/2$. Overall, this gives us a randomized algorithm that finds a cut of expected size $m/2$ in graph $G$.

Exercise 117

In a probability space $(\Omega, {\mathbb P})$, let $X$ be a random variable. If ${\mathbb E}[X] \geq c$, then $X(\omega) \geq c$ for some $\omega \in \Omega$.

Using the implication from Exercise 117, there exists a sequence of coin tossings corresponding to a cut $S$ of size at least $m/2$. This type of result belongs to a broad class of techniques, called probabilistic methods, in which one defines a randomized algorithm that finds a certain object. The success of such randomized algorithm implies the existence of the object we are looking for.

Exercise 118

In this exercise, you will see how to get a slightly larger cut when $n$ is even (i.e., $n=2k$ for some $k \in {\mathbb N}$). We define the following probability space $(\Omega, {\mathbb P})$ where $\Omega = {V(G) \choose k}$ and ${\mathbb P}$ is uniform. That is, each atomic event corresponds to a cut $S \subseteq V(G): |S| = n/2$.

Let $X$ be a random variable denoting the size of the cut. That is, for each atomic element $S \in \Omega$, we have $X(S) = |\delta_G(S)|$. Our goal is to show that ${\mathbb E}[X] > m/2$.

• Define $X = \sum_{e \in E(G)} X_e$ where $X_e$ is the indicator of whether $e \in \delta_G(S)$. Prove that ${\mathbb E}[X_e] > 1/2$.
• Derive that there exists a cut of size larger than $m/2$.

📄️ Derandomization via smaller sample space

One way to turn the above randomized algorithm into a deterministic one is to go over all $S \in \Omega$ and check whether $|\delta_G(S)| \geq m/2$. Since we know that such $S$ exists, our algorithm would always find one. But such an algorithm would take exponential time, since the sample space size is $2^n$.