1
$\begingroup$

This is not homework. I was asked about the following problem by a friend.

Given a graph with $n$ nodes, initially with only one while node and all the rest are black. Each round, nodes are paired in two, and if any one of them is white, then both of them will become (or remain) white. So on average, how many rounds are needed for all the nodes to become white uniformly?

Please help me. Thank you.

  • 0
    Can you only pair adjacent nodes? If not then I don't really see how the graph structure comes into this.2012-05-28
  • 1
    I don't think you can say anything useful in general, because the expectation will depend so strongly on the details of the graph topology and, in non-regular graphs, on which vertex is initially colored white. For example, a line graph of length $n$ will take somewhere between about $n/2$ and $n$ rounds to change, depending on whether the white vertex is in the middle or at the end, whereas a complete graph will change much faster, I guess in something like $\log n$ rounds.2012-05-28
  • 0
    @RobertMastragostino: no, not just only adjacent nodes.2012-05-28
  • 0
    @MarkDominus: OK, let's assume it is complete graph. How to prove your $\log n$ result?2012-05-28
  • 0
    That is a fair question to which I do not have a good answer. I reasoned like this: if the graph is big, then initially the number of white nodes will roughly double at each step, because there will be few white nodes and so the chance that any particular white node will be paired with another white node, rather than with a black node, will be negligible. And once the graph reaches half white nodes, the chance that a black node will be paired with a white node is about 1/2, so the number of black nodes will approximately halve at each step. So it should go like $\log_2 n$ or so.2012-05-28
  • 0
    @MarkDominus: right, that is very good heuristics. But how to make it formal proof?2012-05-28

1 Answers 1

2

This is a case of Randomized Rumor Spreading. Normally, one uses one of the following three models for rumor spreading in graphs:

Push model: In each round, every white vertex calls an adjacent vertex, and colors them white.

Pull model: In each round, every black vertex calls an adjacent vertex, and if they call a white vertex, they become white themselves.

Push/Pull model: In each round, both of the above happen.

When you consider different random graph models, such as the Erdős–Rényi Model, or the Preferential Attachment model, you can get bounds of $\log n$ or better. This also holds for complete graphs.

Actually, there would be cases for your model where the vertices do not become white. Consider for example a path on 4 vertices, where the end vertex is white. In each round, you pick a perfect matching, and there is only one of those. In this case, the other end of the path will never become white.

  • 0
    Thanks for the reference! I actually was just wondering if you could summarize a simple understandable proof for complete graph the $\log n$ bound.2012-05-28
  • 1
    That can be found here: http://www.maths.bris.ac.uk/~maajg/teaching/complexnets/rumours.pdf2012-05-28