Show full work and steps Problem $3.$ Let $G=(V,E,w)$ be a weighted graph, where $w$:$E{R}_{?}0$ is the weight function. By a

cut CsubV we refer to the partition of vertices into $C$ and $\frac{V}{\frac{?}{?}}C.$ The sum of the weights of the edges

in $G$ crossing between $C$ and $\frac{V}{\frac{?}{?}}C$ in $G$ is denoted by ${}_G(C).$

of $G$ if the following holds:

$V(H)=V(G),$ and

for every cut $C,$ it holds $(1-){}_G(C){}_H(C)(1+){}_G(C).$

It is known that there exists an algorithm $S(G,)$ that outputs a $(1+-)$ cut sparsifier $H$ of $G$ such

that $|E(H)|c*\frac{n}{{}^2},$ where $c$ is an absolute constant. Assume that you are given access to $S.$ Assume

that each edge$-$weight of the sparsifier output by $S$ can be stored using poly $logn$ bits.

The following two properties hold:

sparsifier of $G_1{G}_2.$

If $H$ is a $(1+-)$ sparsifier of $G,$ then $S(H,)$ is a $(1+-)*(1+-)$ sparsifier of $G.$

You are given a stream of the edges of a graph $G$ and a parameter $in(0,1).$ Design a semi$-$streaming

algorithm that outputs a $(1+-$ cut sparsifier of $G$ using poly $\{$:$logn)$ bits of memory.

Hints:

You do not need to know anything about graph cuts to solve this problem. We are naming a concrete

problem so that the question is less abstract$.$ Instead of working with graph cuts, we could have

used any other problem with the abovementioned properties.

Think of the stream of edges divided into $T$ chunk, each consisting of $c\frac{n}{{}^2}$ many edges; so$,$ there

are in total $T*c\frac{n}{{}^2}$ edges. Call these edge subyraphs $G_1,G_2,$dots,$G_T.$

Here is a potential approach that is not good enough, but it is good you convince yourself it is

not memory$-$wise efficient. Let $H_1=G_1,$ and $H_i=S(G_i{H}_{i-1},)$; at the time, you store only

the latest $H_i,$ not all of them. Convince yourself that $H_T$ is a $(1+-{)}^{T-1}$ sparsifier of $G.$ Also,

$(1+-{)}^{T-1}$ is roughly $1+-T$ for sufficiently small $,$ and hence you would need to invoke $S$ with

the approximation parameter $\frac{}{T}$ in order for $H_T$ to be $(1+-)$ sparsifier of $G.$ Such a sparsifier

would take up too much space.

The issue with the previous approach is that one graph $G_1$ is repeatedly re$-$sparsified. So$,$ assume

that $T=4.$ Then, the approach above obtains

$\{$:$G_1,),$ and $H_4=S(G_{4}S(G_{3}S(G_2{G}_1,),),),$ yielding $(1+-{)}^3$ sparsifier of $G.$ However,

one can do something else. Let $F_1=S(G_1{G}_2,)$ and $F_2=S(G_3{G}_4,).F_1$ and $F_2$ are $(1+-)$

sparsifiers of $G_1{G}_2$ and $G_3{G}_4$ respectively. Let $F_3=S(F_1{F}_2,).$ Then, $F_3$ is $a(1+-)$

sparsifier of