Show all work and DETAILED work Problem $4.$ Let $A$ be a sub$-$linear memory regime $MPC$ algorithm that, given a graph $H,$ outputs an

$r-$approximate maximum matching in $H$ in $O(T)MPC$ rounds. Given a graph $G,$ design a sub$-$linear

memory regime $MPC$ algorithm $B$ that invokes A multiple times to compute a $(2+)-$approximate

maximum matching in $G.$ Your algorithm $B$ should run in $O(T*\frac{r}{})$ many rounds. Note that A may be

invoked with different graphs in different invocations. When $B$ invokes A with a graph, then A outputs

a set of edges that constitutes an approximate matching of the graph as promised. The execution of $A$

should be treated in a black$-$box way, i$.$e$.,$ we do not have a way to alter $A$ or learn any specifics of it

other than the output we get.

For the full credit, prove that your algorithm outputs a $(2+)-$approximate maximum matching.

In terms of MPC routines, you may assume you have at your disposal all the MPC routines we

mentioned in the lecture and also the following ones that run in $O(1)$ MPC rounds:

Compute the degree of each vertex in a graph.

Given a set of vertices, remove all those vertices from a graph.

Given a set of edges, remove all those edges from a graph.

A remark: The official solution is faster than this problem requires for full credit. That is$,$ the

official solution has $O(T*r*log(\frac{1}{}))$ round complexity.