patternMinor
Proof that fast broadcasts have to target larger cycles first
Viewed 0 times
fasttargetlargerbroadcastsfirstthatcycleshaveproof
Problem
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.
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.
Solution
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):
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):
- $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$
- $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$
- $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)
Context
StackExchange Computer Science Q#12078, answer score: 2
Revisions (0)
No revisions yet.