3
$\begingroup$

I am having trouble trying to formulate a simple proof. I can clearly see that what I am trying to prove is correct but to prove it I am not sure what to do.

The problem is a broadcasting problem on a graph. My graph contains two cycles. The two cycles are joined by a single vertex $v$. If the vertex $v$ contains some info that it wants to broadcast to all other vertices on the graph what is the minimum number of rounds required to achieve this.

So a proof I am trying to formulate is that in order to achieve the minimum broadcast time I would have to first broadcast on the largest of the two cycles.

I was thinking of a proof by contradiction. Something like assume that we first broadcast on the smaller cycle and somehow show that it could lead to a broadcast time that is larger than the time if we were to start on the larger cycle.

To clarify, suppose we have two cycles $C_1$ and $C_2$ such that $|C_1| \ge |C_2|$. So the minimum broadcast time from vertex $v$ denoted by $b(v)$ would require us to broadcast on the larger cycle first.

$\endgroup$
  • $\begingroup$ If i get it right (which I'm really not sure ...) if the two cycles are disjoint except for v then the one you begin with does not matter, you will have to do the other one anyway ... $\endgroup$ – wece May 16 '13 at 17:08
  • $\begingroup$ Yeah I understood that, but you want all the vertices to get the information right? so let $b_1$ be the number needed for cycle $1$ and $b_2$ for cycle $2$ since the two cycles are disjoint you need $b_1+b_2$ if you start by cycle $1$ and $b_2+b_1$ if you start by the second ... Or may be there is something I still don't get. $\endgroup$ – wece May 16 '13 at 17:17
  • $\begingroup$ Thick of it as in discrete rounds. Each round an informed vertex can inform one of its uninformed neighbours. So the larger of the two cycles will take longer to inform all it's vertices than the smaller cycle. I am trying to figure out the minimum broadcast time. $\endgroup$ – gprime May 16 '13 at 17:22
  • $\begingroup$ ok get it sorry. So yes start with the larger one (say $C_1$) the time will be $b_1+1$ whereas if you start by $C_2$ you will have $b_1+1+1$ on to broadcast to $C_2$ the second to broadcast to $C_1$ and then $C_2$ will finish before $C_1$ and $C_1$ take $b_1$. That what you had in mind? $\endgroup$ – wece May 16 '13 at 17:30
  • $\begingroup$ Yeah, pretty much. Now how to structure the proof... $\endgroup$ – gprime May 16 '13 at 17:50
2
$\begingroup$

Let $b_0$ be the minimal broadcasting time of an information from vertex $v$ to the cycle $C_0$ and $b_1$ be the minimal broadcasting time of an information from vertex $v$ to the cycle $C_1$.

Remark that since $C_0$ and $C_1$ are cycles the fastest way to broad cast is for $v$ to broadcast first one of his neighbor and then the other.

Since $C_0$ and $C_1$ are only connected by $v$ and $v$ already have the information we know that spreading the information through $C_i$ will not improve the minimal broadcasting time for $C_{1-i}$.

3 cases (first one developed the others just ideas):

  1. $b_0>=b_1+2$ (hence $|C_1|>|C_2|+3$) if $v$ start broadcasting his two neighbor in $C_0$ and then those of $C_1$. The time the information reach the last vertex in $C_0$ will be $b_0$ and the last vertex in $C_1$ $b_1+2$ hence $b_0$ in total. And you can't do better by definition of $b_0$
  2. $b_0=b_1+1$ if you start twice by $1$ you will do at best $b_0+2$ and you do better by choosing $0$
  3. $b_0=b_1$ it doesn't really matter but if the parity of the two cycle is different you may want to start by the odd one (or even not sure :D)
$\endgroup$
  • $\begingroup$ thanks, i might be able to use some of this in my proof. $\endgroup$ – gprime May 21 '13 at 17:26

Your Answer

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

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