On a graph $G(V,E)$, we do the following process:
- Initially, all nodes in $V$ are uncolored.
- While there are uncolored nodes in $V$, each uncolored node does the following:
- Selects a random real number and sends it to all its neighbours;
- Compares its number to the number of its neighbours; if its own number is strictly smallest, then the neighbour paints itself red and notifies all its neighbours.
- If a neighbour became red, then this node paints itself black.
- Suppose the graph is a path: a-b-c-d-e.
- Suppose the numbers in the first step are: 1-2-0-3-4.
- Nodes a and c are painted red; nodes b and d are painted black.
- In the second step, only node e remains uncolored; it is trivially minimal so it paints itself red.
MY QUESTION IS: what is the average number of steps that this process takes before all nodes are colored?
My current calculation leads me to an $O(1)$ estimate, which seems too good to be true. Here is the calculation:
Consider a node $v$ with $d$ neighbours. The probability that $v$ will be the smallest among its neighbours is $1/(d+1)$. If this happens, then $v$ and all its neighbours will be colored. So the expected number of vertices colored each step is $(d+1)/(d+1)=1$ per node. Hence the total expected number of vertices colored each step is $O(n)$, so in $O(1)$ time all nodes will be colored.
If this analysis is wrong (which is probably the case), then what is the actual number of steps?
But, I am still not convinced that this analysis is tight. In all graphs I checked, it seems that the algorithm completes in $O(1)$ expected time.
My question is now: what is a worst-case graph in which this algorithm indeed requires $O(\log n)$ steps in average?