4
$\begingroup$

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
neighbors.
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.

$\endgroup$

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.