Algorithm Design in the MPC Model

Approach: We'll employ a randomized algorithm for MIS in the MPC model inspired by Luby's algorithm, which is parallelizable and provides an efficient way to find a maximal independent set. Our adaptation will ensure the algorithm is suitable for execution in a distributed environment like MPC$.$

$1.$ Algorithm Outline:

Initialization: Distribute the graph's vertices and their respective adjacency lists across the available machines.

Iteration:

Each vertex independently decides whether to join a candidate set with a certain probability.

Each machine checks its local vertices and flags a vertex if any of its neighbors also decided to join the candidate set.

Vertices that are not flagged $($i$.$e$.,$ none of their neighbors are in the candidate set$)$ are added to the independent set.

Remove these vertices and all their adjacent edges from consideration in subsequent rounds.

Termination: The process repeats until no more vertices can be added to the independent set.GIVE MATHEMATICAL CORRECTNESS OF THIS ALGORITHMS