There are a couple of randomized parallel algorithms for the maximal independent set problem, e.g. A Simple Parallel Algorithm for the Maximal Independent Set Problem, A fast and simple randomized parallel algorithm for the maximal independent set problem.

These algorithms were the (or one of the) first examples where $k$-wise independent events/random variables are used to derandomize parallel algorithms. One algorithm (which is described here in the chapter "Fast MIS v2") works as follows:

The algorithm operates in synchronous rounds, grouped into phases.
A single phase is as follows:
1) Each node v chooses a random value r(v) from [0,1] and sends it to its
2) If r(v) < r(w) for all neighbors w in N(v), node v enters the MIS and
informs its neighbors.
3) If v or a neighbor of v entered the MIS, v terminates (v and all edges
adjacent to v are removed from the graph), otherwise v enters the next phase.

My question: Is it known that this algorithm also works if the random values are $k$-wise or even pairwise independent?

I didn't find anything in the literature but maybe I just miss something.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.