Peer Sheet 4

P4.1 Randomized Algorithms

Algorithm: We assign each vertex independently and uniformly one of the $k$ colors and keep only the valid edges (edges that have different colors on the two ends) We repeat this step until we find a solution such that $|E^{\prime }|>\frac{k-2}{k}|E|$ Proof: we define event $E_i:=$ edge $i$ has same colors on both ends $F_i:=$ edge $i$ has different colors on both ends $\mathrm{Pr}[E_i]=\frac{1}{k}$ since the colors of the vertices are chosen indepently and uniformly $\mathrm{Pr}[F_i]=1-\mathrm{Pr}[E_i]=\frac{k-1}{k}$

Let $F$ be the number of edges that have different colors on both ends $\mathbb{E}[|E^{\prime }|]=\mathbb{E}[F]={\sum }_{i=1}^{|E|}\mathrm{Pr}[F_i]=\frac{k-1}{k}|E|>\frac{k-2}{k}|E|$

Time analysis: Each trial takes $O(|V|+|E|)$ (we assign each vertex a color and check each edges) Let $R:=$ the number of repetitions of the trials with $\mathbb{E}[X]=\mathbb{E}[R]\cdot O(|V|+|E|)$ We know each trial succeeds with probability $p>0$ then $R$ is geometric distributed with $\mathbb{E}[R]=\frac{1}{p}$ $⟹\mathbb{E}[X]=\Theta (1)\cdot O(|V|+|E|)=\Theta (|V|+|E|)$