More recent questions will be at the beginning
(top) of the page.
Q&A regarding the material in class:
On Thu,
> Yehuda shalom,
>
> the
meaning is that v and u are not being colored seperately
and
> independently!
> they
are colored together, and then when i move to a
neighbor w of u, i have
> to
> consider the color of u, which
has already been determined.Is it true
?
>
NO.
When you color v, you do
not think of any other node. It is a
completely independent process. Only when you want
to prove that the coloring
is legal you show that the algorithm must have
chosen different colors for v
and u (by observing the ring from the
previous email). Notice that v can have many neighbors.
To prove that the coloring
of v does not collide with any of its neighbors
colors you use many different
rings with different sequences of ids.
Yehuda shalom,
>
> there
is a something that i havn't
understood yet :
> you
wrote me :
> "Each time we color a node
we take a new copy of a ring (simulating the
> ring on the side) assign the
2t+1 sequence of ids from the node label to
> nodes
on the Ring and figure out what will be the color of the node in the
> middle
of the 2t+1 sequence. This color is then
given to the
> corresponding node in G(2t+1)....."
>
> my
question is :
> if
there is an edge from v to u in G(2t+1), and i color
now v, does the
> coloring
of v have influence on the coloring of u ?
> if
not, the meaning is that the nodes are colored independently, so why
> can't two nodes be colored the
same ( without any connection to the prove of
> the coloring
) ?
The label of v in G(2t+1) is [x1, x2, ...., xt,
xt+1, ..., x2t+1],
u neighbor of v label
is [x2, x3, ...., xt+1, xt+2, ...,
x2t+2].
In any ring in which a
sequence of nodes have the ids:
..., x1, x2, x3, ...., xt, xt+1, xt+2, ...., x2t+1, x2t+2, .... the
algorithm 6-colors node xt+1 and
node xt+2 with different colors,
therefore the colors of v and u are
different in G(2t+1).
First consider the answer
to your second question and then the answer
to your first question.
2. Coloring a node in G(2t+1):
The assumption is that
there is a t rounds algorithm to 6-color nodes in a ring.
After t rounds of such an
algorithm on a
ring, each node on the ring
was affected only by nodes that are at
distance t or less from it. I.e., given the t nodes on each side of it, a
node in
the ring can tell what would
be its coloring in the Ring coloring
algorithm. Now, we use this coloring to color the nodes
of G(2t+1).
Each time we color a node
we take a new copy of a ring (simulating the
ring on the side) assign the
2t+1 sequence of ids from the node label to
a continuous stretch of
nodes on the Ring and figure out what will be
the color of the node in the
middle of the 2t+1 sequence.
This color is then given
to the corresponding node in G(2t+1).
Now to your first
question, why is this a legal coloring:
Because first observe that
the sequence of ids in the label of one node in
G(2t+1) is a shift by one of
the sequence of its neighboring node, with one
new id poping
on the right. Therefore, to prove that
this is a legal coloring,
we take a ring and put the
union of these two labels (i.e., a sequence of length
2t+2) on a ring and run
the 6-coloring algorithm, then the color of
each of the two nodes in
G(2t+1) should be legal
since the coloring in the ring is legal.
On Wed,
> Yehuda shalom,
> i have two more questions:
>
> 1. u wrote me : "To fix the color of v...."
> i understand that each node is colored independently, so how can i
> promise that 2 neighbours won't be colored by the same color ?
>
> 2. why do i need t nodes from each side(of x(t+1)), when i color a node v ?
>
> thanks,
> my
SECOND question is, again :
>
> given an algorithm A for ring's
6-coloring in t iterations(a "black box"),
> how
can i color G(2t+1) in 6 colors?
Recall that each node in G(2t+1) is labeled with a sequence of 2t+1
Ring-node-ids. To fix the color of node v in G(2t+1) whose label is [x1,
x2, ..., x(t+1), ...,
x(2t+1)] construct a ring with more than 2t+1 nodes,
and assign the ids x1, x2,
..., x(2t+1) to a continuous sequence of 2t+1 nodes
on the ring. Now run A on the ring you have just
constructed and color
node v with the color of node
x(t+1) on the constructed ring. Claim,
this
is a 6 coloring of
G(2t+1). Prove this claim by
contradiction: notice you
can construct a ring with a
sequence [x1, x2, ..., x(2t+2)] of 2t+2 ids
on the ring such that the
colors of v and its neighbor in G(2t+1) are the
colors of two neighbors on this
ring.
>
> thanks,
Notice there is a new solution on the web site for the Question 2 in HW 1. http://www.cs.tau.ac.il/~afek/solution1.103.html
> Yehuda shalom,
> and my
questions are :
Answers below,
and I hope to give again an overview in class next week.
> 1. in
the last lesson, you actually proved that MIS cannot be maid in T
> iterations,
> when T is
constant, but you did not proved that it cannot be maid in
> less
then log*n
> iterations. is it true ?
We actually proved that
there is no algorithm to color a ring (in
the model that we discussed,
synchronous, unbounded message size) with 6
colors in less than log^* n
(denoted log*n). This is denoted o(log*n), i.e., there is no
algorithm that colors a ring with 6
colors in o(log*n) (little o notation).
We did it by establishing
two facts:
1. that if there is
such
an algorithm that color a
ring with 6 colors in t<log*n then we can color
graph G(2t+1) (as defined in
class) with 6 colors. and
2. that the chromatic
number of G(h) greater equal log^h(n) (=log log
log ... log n, taking log h times), and therefore in order
for the chromatic number
of G(h) to be constant (like
6) h must be in the order of log*n (e.g.,
some constant times log*n, say
2 log*n). Notice that this completes
the
proof by the following
argument:
By contradiction: Assume
you have an algorithm A that colors
the ring with 6 colors in t'
such that t'< log*n then I color G(t') with
6 colors
a contradiction to point 2. Notice we
make no assumptions on A,
which makes the proof a strong
one. E.g., no assumption on message
size.
> 2. i did not understand how you can use the MIS
algorithm to color G(2t+1)
> in 6
> colours.can
u explain this again ?
>
> thanks,
In class I argued the
other way around. That is, that
given a 6 coloring of the ring
then I can easily construct an MIS, as
follows: Say the colors are c1, c2, c3, ..., c6. Then I have 5 more
rounds, round-1, round-2,....
after we 6 color the ring: In round-i,
i=1,...,5
all the nodes with color ci which are not yet marked
OUT mark
themselves IN and tell all their
immediate neighbors to mark themselves
OUT. Claim (prove it to yourself) after the 5th
round the IN marked nodes
are an MIS.