8
$\begingroup$

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.

For example:

  • 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?

EDIT: As noted by @JukkaSuomela, the algorithm described above is due to Metivier et al, 2011 and is explained and analyzed in these lecture notes. They prove that the run time is $O(\log n)$.

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I guess you are aware that this is the algorithm presented and analysed in Section 2 of Métivier et. al (2011)? $\endgroup$
    – Jukka Suomela
    Feb 21, 2015 at 0:43

1 Answer 1

Reset to default
3
$\begingroup$

There is a minor mistake, the probability of $v$ being minimal is $1/(d+1)$. That doesn't change anything, but it is still worth pointing out.

The problem is that the events you are summing aren't disjoint. Consider two vertices that aren't adjacent but have a common neighbour. If both vertices end up being minimal amongst their neighbours, then the common neighbour gets counted as being coloured twice.

We need to examine what happens in a vertex more closely. Let's compute the probability (and thus expectation of the indicator variabele) of a single vertex getting coloured.

Assume for the sake of analysis that the graph is $d$-regular and contains no triangles or squares. We will compute the chance that a given vertex $v$ does not get coloured. There are $d+1$ possibilities: the $v$ might be the smallest amongst it neighbours, $v$ might be the second smallest, third smallest, and so on... We are not interested in the case that it is the smallest, since then it gets coloured.

If $v$ is the second smallest, there is one vertex that is smaller. The probability of this vertex being smallest amongst its neighbours is $\frac{1}{d}$ (and thus $v$ getting coloured). The probability of the remaining neighbours being smallest amongst their neighbours is 0 (since $v$ is smaller). The total probability (of $v$ not getting coloured) from this case is $\frac{1}{d+1}\cdot\frac{d-1}{d}$.

If $v$ is third smallest, there are two smaller vertices. The probability from this case is $\frac{1}{d+1}\cdot(\frac{d-1}{d})^2$.

Continuing on like this, we find that the probability that $v$ does not get coloured is $\frac{1}{d+1}\Sigma_{i=1}^d (\frac{d-1}{d})^i$. The probability of a given vertex getting coloured is thus $1-\frac{1}{d+1}\Sigma_{i=1}^d (\frac{d-1}{d})^i$. As $d\to \infty$, the probability becomes $\frac{1}{e}\approx 0.368$.

Hence the probability that a given vertex gets coloured is a constant, so the expected number of vertices that gets coloured in the first step is indeed $O(n)$.

That does not make the algorithm $O(1)$. Assuming the probability stays constant (which is not entirely justified considering nodes get coloured and no longer participate in the algorithm, the graph does not remain $d$-regular), in the $k$-th step there will be (in expectation) ${(\frac{1}{e})}^kn$ uncoloured nodes. The decay is exponential, so the algorithm takes $O(\log n)$ steps.

Perhaps somebody else will be able to offer a more precise analysis, but from my argumentation it seems likely the algorithm is $O(\log n)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The problem with this argumentation is that, as you said, the degree of each node strictly decreases at each step, as other nodes are removed. So, the probability that a node is selected increases, the decay may be faster than exponential, and the run time may less than $\log n$. Do you have an example graph where the number of steps is $\Theta(\log n)$? $\endgroup$
    – Erel Segal-Halevi
    Feb 20, 2015 at 9:21
  • $\begingroup$ @ErelSegalHalevi That isn't the problem. By my argumentation, as the degree decreases, the probability of a node getting colored never becomes greater than 0.75 (which is the value for a 2-regular graph, a 1-regular graph always gets colored instantly). Asymptotics don't really care if the probability increases, so long as (for sufficiently large $n$) you can bound it by a constant. The problem is that I've only been able to calculate this figure for regular, triangle- and square-free graphs. $\endgroup$
    – Tom van der Zanden
    Feb 20, 2015 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.