Transcript WLATreeAlltoAll

Coloring Paths in Directed
Symmetric Trees with Applications
to WDM Routing
By L. Gargano, P. Hell, S. Perennes
Presented By: Gal Ostfeld
A Tree
Definition:
Let G (V,E) be a graph.
G is called a “tree” if it’s connected and circuit-free.
Also:
• Any new edge added to G will form a circuit.
• Every 2 vertices have a unique path connecting them.
• If any edge is deleted the connectivity of G is
interrupted.
• |E| = |V|-1.
A Symmetric Directed Tree
Equivalent to an undirected tree with each
edge viewed as two opposite arcs.
A Dipath
• Let T be a tree and x,y two vertices of T.
• The “dipath” P(x,y) in T is the undirected path
joining x to y, in which each edge is considered
traversed in the direction from x to y.
• The dipaths P(x,y) and P(y,x) are different and do not
traverse any edge in the same direction
Dipaths P(x,y) & P(y,x)
P(x,y)
x
P(y,x)
y
Our Goal – The All to All Problem
(AKA “Gossiping”)
Coloring the set of dipaths P(x,y), for all
ordered pairs x,y of vertices of T, in such a
way that two dipaths using the same edge of
T in the same direction obtain different
colors with minimum number of colors (This
way is called “proper” coloring).
So, what’s “proper”?…
Then, what’s not “proper”?…
We shall prove that…
• Given c(T) is the minimum number of colors in
such a coloring of the dipaths in tree T.
• Given (T) is the maximum number of dipaths
P(x,y) which all pass through the same edge of
T in the same direction.
c(T) = (T)
A weighted Tree
• A weighted Tree is a tree T with positive
integer weights w(x) on the vertices x of T.
(The intention is to have a w weight vertex
represent w unweighted vertices)
• The total weight of a set X of vertices of T is
w(X)= w(x) => w(T) is tree weight.
x X
Load / Maximum Load
Let e be an edge in a weighted tree T.
The removal of e from T results in two weighted
subtrees T1 and T2 .
• The “load” of e is the product w(T1)w(T2)
• The “forwarding index”, (T), is the maximum
load of any edge in T.
(when all w(x) = 1, (T) is the maximum number
of dipaths P(x,y) which all pass through the
same edge of T in the same direction)
Minimum Number of Colors
In a weighted tree T, the “multiset of all dipaths”
consists of the w(a)w(b) copies of the dipath
from a to b for every ordered pair of vertices
a,b.
• c(T) is the minimum number of colors in a
proper coloring of the multiset of all dipaths.
(when all w(x) = 1, c(T) is the minimum number
of colors in a proper coloring of the set of all
dipaths)
In(v) / Out (v)
Let v be a vertex in a weighted tree T.
• In(v) consists of the dipaths from the multiset
of all dipaths which end with v.
• Out(v) consists of the dipaths from the multiset
of all dipaths which begin with v.
Theorem
•Any weighted tree T satisfies c(T) = (T).
•And there exists an efficient algorithm
which colors T with c(T) colors.
Proof:
Inductively…
Definitions:
w(x)>δ
•
•
•
•
•
T – weighted tree
w(T) = W
x - leaf of T
f - parent of x
δ - integer, 0<δ<w(x)
x
f
w(T) = W
T
Definition: AddLeaf
• AddLeadδ(x) modifies T as follows:
– w(x) = w(x) – δ
– A new node y is added:
• w(y) = δ
• connected to x
x w(x)
f
δ
y
w(x)
w(x)–δ
f
x
Definition: SplitLeaf
• SplitLeadδ(x) modifies T as follows:
– w(x) = w(x) – δ
– A new node y is added:
• w(y) = δ
• connected to f
x w(x)
f
w(x)–δ
x
w(x)
f
δ
y
Definition: Legal actions
AddLeaf or SplitLeaf are “legal” if
w(x)W/2 (δ+w(x)  W).
Lemma 1
• If AddLeaf is legal then in the new tree the
load of [x,y] cannot be larger than the load
of [x,f] in T.
• If SplitLeaf is legal then in the new tree the
load of [x,f] and [y,f] cannot be larger than
the load of [x,f] in T.
Lemma 1 Proof
n*(W-n)
δ
Add
Max = W/2
w(x)–δ
w(x)- δ
δ
y
x
f
w(x)
n
Finding the max:
(n*(W-n))’ = 0
W-2n = 0
n = W/2
Before
Add/Split
Split
w(x)–δ
x
f
After
Add/Split
y
δ
Lemma 2
If AddLeaf or SplitLeaf on T is legal then the
forwarding index of the new tree doesn’t exceed
the forwarding index T.
Proof:
Trivial – based on the preceding lemma.
Definition: W/C Tree
Let T be a weighted tree.
Let w(T) = W.
• T is called a “W/C tree” if the two trees
resulting from the removal of an edge of
maximum load have weights C and W-C, with
C≥W/2.
In a W/C tree: (T) = C(W-C)
Definition: W/C Star
In case a W/C tree is a weighted star then T
is called a “W/C star”.
In a W/C star the maximum load on an edge
leading to a leaf is (T)=C(W-C).
What are we trying to achieve?
Given a W/C Tree, T.
• We shall recursively reconstruct T from
some initial W/C star S, with AddLeaf and
SplitLeaf legal operations.
• In the W/C star S: (S) = C(W-C)
• By Lemma 2, eventually we’ll get
(T) = (S) = C(W-C)
Lemma 3
A W/C tree T can be generated from some
W/C Star T* by repeated applications of
legal operations of AddLeaf or SplitLeaf
Lemma 4
(Needed for lemma 3’s proof)
Any W/C tree T contains a vertex u such that the
maximum weight of a component of T\{u} is W-C.
Proof:
We know that exists an edge e1 (between vertices
u1 and u2) that divides T to T1 and T2 (respectively)
that hold w(T1)=C, w(T2)=W-C.
Let’s choose u1 and prove its suitable for our
“needs”.
Lemma 4 Proof
T1
W(T1)=C
Ti
W(T2)=W-C
u3
e2
Tj
Tk
u1
e1
u2
T2
w(T2)=W-C, by definition.
Let’s assume w(Ti)>W-C,
for example: w(Ti)=W-C+n=W-(C-n).
T is a W/(C-n) tree (via the e2 edge).
Contradicts T being a W/C tree (since (C-n)(W-(C-n))>C(W-C).
All Ti-s “inside” T1 should hold w(Ti)<=W-C. QED
Construction of W/C tree T’s
W/C star T*
• Start with a W/C star T* consisting of the
vertex u and all its neighbors in T.
• Each neighbor v, should have his w(v) set to
the weight of the component of T\{u} that
contains v.
W/C tree T’s W/C star T*
T1
W(T1)=C
Ti W(Ti)=D
W(T2)=W-C
u
W(Tj)=E
Tj
T2
W(Tk)=F
Tk
W(ui)=
D
ui
W(uj)=E
W(u2)=W-C
u
uj
W(uk)=F
uk
u2
From W/C star T* to W/C tree T
Let t be the number of nodes in T which are
not adjacent to u.
• If t=0 then T is a star and we’re done!
W(ui)=D
W(u2)=W-C
ui
W(uj)=E
u
uj
W(uk)=F
u2
uk
So, we have the induction base.
From W/C star T* to W/C tree T
Suppose that the result holds for if t<=k.
Let t=k+1. (Induction Step)
Let z be a leaf of T of maximum distance from
u, and let p be z’s parent.
• If degree(p)=2 then Let T’ be the weighted
tree obtained from T by removing z and
increasing w(p) by w(z).
• T is generated from T’ by AddLeafw(z)(p).
From W/C star T* to W/C tree T
(When degree(p)=2)
T’
T
w(z)
w(p)+w(z)
f
p
[w(p)+w(z)]–w(z)
f
z
p
From W/C star T* to W/C tree T
• If degree(p)>2 then Let x be a leaf neighbor
of p other than z. Let T’ be the weighted tree
obtained from T by removing z and increasing
w(x) by w(z).
• T is generated from T’ by SplitLeafw(z)(x).
From W/C star T* to W/C tree T
(When degree(p)>2)
T’
T
w(x)+w(z)
x
p
[w(x)+w(z)]–w(z)
p
w(z)
Lemma 3 QED
x
z
Lemma 5
The multiset of dipaths of any W/C star can
be efficiently colored with C(W-C) colors.
Hall’s Marriage Theorem
(Needed for lemma 5’s proof)
Let’s have two sets of N elements denoted M, F.
Each of the elements in M is willing to “marry” a
number of elements from F.
• If for every K sets from M, 1<=K<=N, the
number of elements from F is at least K, then
we would have a perfect matching, i.e. we can
choose N couples according to the “wish list”.
Hall’s Marriage Theorem Example
M
5x
F
Lemma 5 Proof
• In a star two dipaths conflict if and only if they
have the same beginning or the same end.
• Two dipaths of the same color must belong to
two different multisets In(v) and to two
different multisets Out(v).
• For each vertex v |In(v)| = |Out(v)|.
• This size differs from vertex to vertex.
• Maximum In(v) per edge = C(W-C).
Lemma 5 Proof - continued
• Add to each In(v) and Out(v), at each vertex v,
C(W-C)-|In(v)| artificial nodes (consisting only
of v).
• Denote the set of all In(v)-s as Hall’s Theorem’s
M.
• Denote the set of all Out(v)-s as Hall’s
Theorem’s F.
• Denote “exists a dipath that begins in Out(v)
and ends in In(v)” as Hall’s Theorem’s “willing
to marry”.
Lemma 5 Proof – Step #1
Out(v1)
C(W-C)
C(W-C) …
In(v1)
…
Out(v2)
…C(W-C)
…
… C(W-C)
In(v2)
nx
Out(vn)
C(W-C)
…
…
…
C(W-C)
In(vn)
(By color #1)
Lemma 5 Proof - end
• Since all the Out(v)-s have C(W-C) out edges,
and In(v)-s have C(W-C) in edges, every K
Out(v)-s point to at least K different In(v)-s.
• After matching each In(v) with an Out(v)
perfectly, we use color #1 to “marry” them.
• Then we can delete from consideration the
edges we used for the matching.
• Now we have the same problem, but with one
less edge from/to each node.
• We can go on, till all the edges are used.
• We used C(W-C) colors. QED
Going On...
(Some definitions)
Let x be a fixed leaf in tree T (on which we shall
perform the legal AddLeaf, SplitLeaf).
T is properly colored.
In(x) (with the In set of colors) and Out(x) (with the
Out set of colors) might have used different colors.
|In|=|Out|
• Let “” be the fixed bijection between Out and In,
such that for any c belonging to OutIn, (c)=c.
And On...
(Some more definitions)
Let z be any vertex of T\{x}.
All the w(z)*w(x) dipaths between x and z must
obtain different colors, since there’s a unique edge
out (in) of (to) x (x is a leaf).
• Arbitrarily fix (for each z) a partition of these
w(z)w(x) colors into w(z) classes of size w(x)
denoted O1z, O2z …, Ow(z)z (I1z, I2z …, Iw(z)z).
• We shall say that two colors on dipaths ending
(starting) in x are “I-equivalent” (“O-equivalent”) if
they belong to the same class Iiz (Oiz).
And On...
(And more definitions)
• A “supercolor” is a set U of colors such that
no colors from U are I-euivalent, and no
colors from (U) are O-euivalent.
• Let X be the set of w(x)(W-w(x)) colors
used by the dipaths starting in x.
Lemma 6
The set X of colors can be partitioned into
w(x) supercolors.
Lemma 6 - Proof
• Let Ei (1iW-w(x)) be the I-equivalence classes
of x on X.
• Let Fi (1iW-w(x)) be the O-equivalence classes
of x on X.
• Let E’i=(Ei) (1iW-w(x)).
• Denote the set of all E’i-s as Hall’s Theorem’s M.
• Denote the set of all Fi-s as Hall’s Theorem’s F.
• Denote “a color exists both in E’i and in Fi” as
Hall’s Theorem’s “willing to marry”. QED
Lemma 6 Proof - Illustration
E’1
w(x)
…w(x)
…
w(x) …
F1
…
E’2
w(x)
…
… w(x)
F1
(W-w(x)) x
E’W-w(x)
…
…
w(x)
FW-w(x)
(x w(x) colors)
Proposition 7
Let T be a W/C tree. With a proper coloring of
its multiset of all dipaths.
T’ is obtained from T by performing the legal
operation AddLeaf or SplitLeaf.
• T’ is a W/C tree which also admits a proper
coloring of its multiset of all dipaths.
Proposition 7 Proof
• Partition the colors into w(x) supercolors.
• Partition the supercolors into S1, S2 such that
|S1|=w(x)-δ and |S2|=δ.
• Perform AddLeafδ(x) (SplitLeafδ(x)) on T, to
create node y.
• Let T’\{x,y} be T~.
• Use S1 to color the paths from (to) x to (from) T~.
• Use S2 to color the paths from (to) y to (from) T~.
• If we dealt with a SplitLeaf operation – we’re
done!
Proposition 7 Proof
• If we dealt with an AddLeaf operation, we must
check if we have enough supercolors to color the
new dipaths between x and y (both directions).
• We used δ supercolors [=w(T~)*δ colors] to color
the dipaths between y and T~ (both directions).
• The w(x)- δ supercolors [=w(T~)*(w(x)-δ) colors]
to color the dipaths between x and T~ (both
directions), can be reused for the dipaths between
x and y (different edge of x).
Proposition 7 Proof
• There are w(x)-δ supercolors [=w(T~)*(w(x)-δ)
colors] left to color the dipaths between x and y
(both directions).
• We need δ(w(x)-δ) colors to color the δ(w(x)-δ)
dipaths between x and y (both directions).
• δ < w(T~) (it’s a legal operation).
• δ(w(x)-δ) < w(T~)*(w(x)-δ). QED
Proposition 7 Proof - Illustration
x w(x)
f
w(x)–δ
w(x)
f
δ
δ
x w(x)
f
x
y
y
w(x)
w(x)–δ
f
x
cs(T)
• cs(T) = The minimum number of colors in a
coloring of the paths from a subset S of all the
paths on a directed symmetric tree T, such that
conflicting paths obtain different colors.
• In the general situation of an arbitrary set S of
dipaths, it’s known that the problem of optimally
coloring the paths in the set is NP-hard.
• Only approximation algorithms are known.
• We shall consider cases in which cs(T) can be
efficiently evaluated.
T Is A Path
• “Proper vertices coloring” = Coloring of the
vertices, such that adjacent vertices obtain
different colors.
• “Chromatic number” = The minimum number of
colors in such a coloring of the vertices in tree T.
• If T is a path, cs(T) is equivalent to the fact that
for an interval graph the chromatic number is
equal to the maximum clique size.
Path Coloring
6
1
4
2
Clique Number = 4
5
3
2
3
1
4
5
1
4
5
2
6
Clique Number = 3
3
2
3
4
5
1
T Is A Star
• “Proper edges coloring” = Coloring of the edges,
such that adjacent edges obtain different colors.
• “Chromatic index” = The minimum number of
colors in such a coloring of the edges in tree T.
• If T is a star, cs(T) is equivalent to the fact that
for a bipartite graph the chromatic index is equal
to the maximum degree.
Star Coloring
Maximum Degree = 3
1
2
2
3
3
4
4
5
5
2
1
5
3
1
4
A Conflict Graph
The “conflict graph” of set of paths S on a tree T
is the undirected graph whose vertices are the the
dipaths from S, and two dipaths are adjacent if
and only if they conflict, i.e. use an edge of T in
the same direction.
5
1
2
3
4
5
6
1
6
3 2
4
A Generalized Star
It’s a tree obtained from a star by replacing each
edge with a path (the paths may have different
lengths).
Facts About Generalized Stars
• A generalized star is a tree in which at most
one vertex has a degree greater than two.
• Any tree in which at most one vertex has a
degree greater than two is a generalized star.
• Stars and paths are generalized starts.
Odd Hole / Odd Antihole
• An “odd hole” of an undirected graph is an
induced cycle without chords, of odd length
greater than three.
• An “odd antihole” of an undirected graph is an
induced complement of a cycle without chords,
of odd length greater than three.
Lemma 8
The conflict graph of any set of paths on a
generalized star cannot contain an odd hole
or an odd antihole.
Lemma 8 Proof – Odd Holes
• Let “c” (for center) denote the vertex with degree
more than two (if exists).
• Let “A type” be a path traversing via the c.
• Let “B type” be a dipath which is not an A Type.
• Let P1,…,Pm (m>3) be such that their conflict
graph forms an odd hole, i.e. Pi conflicts with Pi-1
and Pi+1 (cyclically) for any 1im.
• P1,…,Pm cannot be all B Types, since the closest
one and the farthest one from c cannot conflict
without conflicting with all other dipaths.
All B Types - Illustration
The red dipaths conflict with only one dipath.
c
Lemma 8 Proof – Odd Holes
• A types can conflict either in both of their first part
(before c) or in both of their last part (after c).
• In a hole there must be an even number of A types.
Even A Types - Illustration
The red dipath is needed to complete the hole.
c
Lemma 8 Proof – Odd Holes
• There can be no B types between any two A
types, because either the B types conflict with
only one of them, so that A type conflict with
at least three dipaths (and that’s not a chordless
hole), or the B types conflict with both of
them, so both A types conflict with at least
three dipaths (and that’s not a chordless hole).
• If there can be no B types and there can only
be an even number of A types, any conflict
graph’s hole must be even.
B Types Between A Types Illustration
The red B types conflict with both A types.
3 conflicts
1
2
3
c
2
1
3
3 conflicts
The purple B types
conflict one A type.
Lemma 8 Proof – Odd Antiholes
• An antihole can be viewed as some general
case of a hole (when n=5):
– Each vertex has the exact same number of
neighbours (n-3 in an antihole, 2 in a hole).
– It has a sense of direction.
a
a
b
c
d
e
=
d
e
c
b
Lemma 8 Proof – Odd Antiholes
• We’re left with antiholes of size  7.
• Its complement is a hole of size  7.
• Its complement has a chordless path on  6
vertices.
• But a conflict graph’s complement cannot
contain a chordless path on  6 vertices. QED
Corollary 9
For any set S of dipaths in a generalized
star T we have cS(T)=S(T).
Corollary 9 Proof
• A graph is perfect if (and only if) it contains no
odd hole and no odd antihole (The perfect
graph conjecture).
• Conflict graphs in generalized stars are perfect.
• cS(T)=S(T). QED
Proposition 10
cS(T)=S(T) for all sets S on T if and only if T
is a generalized star.
Proposition 10 Proof
• T isn’t a generalized star.
• T contains at least two vertices of degree  3.
• Let’s build the following S:
cS(T)=3
S(T)=2
• And since we’ve proved that for a generalized
star cS(T)=S(T). QED
Well Distributed Set of Paths
Let T be a tree.
Let S be a set of paths in T.
• S is “well distributed” in T if T does not
contain an odd number of edges [v,a1],
[v,a2],…, [v,a2k+1] such that some dipath of
S contains both edges [v,ai] and [v,ai+1] (in
some direction, addition on index is taken
modulo 2k+1), for any index i= 1,…2k+1.
Proposition 11
If S is well distributed in T then cS(T)=S(T)
and cS(T) can be found in polynomial time.
Proposition 11 Proof Intuition
• Let’s look at what was the “problem” in the
beneath example:
cS(T)=3
S(T)=2
• Although all the non-dashed edges were all used
only in one direction, the dashed edge was used in
both, in a way that it “mixed” the constraints of
paths from different edges (or from similar edges
but from different directions, in the general case).
Proposition 11 Proof Intuition
• So, let’s try and see how we can keep apart
constraints on different edges and on different
directions on each edge.
• We shall first show that if S is well distributed in
T, then T admits an orientation such that each
dipath in S either uses all edges in the chosen
direction, or all in the opposite direction.
• And since those two “groups” of paths cannot
conflict, we can color them separately.
• Then we shall easily see that for each set
cS(T)=S(T).
Proposition 11 Proof
• Let’s say that S is well distributed in T.
• Either there’s a cycle as in the well distributed
definition, but with even size (instead of odd).
Red group – in the
“chosen direction”
Blue group – in the
“opposite direction”
Black Arrowheads –
The edges’ “directions”.
Dashed line – spoils
well distribution.
• If both paths’ common edge is in the same
direction we shall put both of them in the same
“group”, else in two different “groups” – The
even size, assures that the “last” path can agree
(disagree) with both “neighbors” together.
Proposition 11 Proof
• Or there isn’t a cycle as in the well distributed
definition.
Red group – in the
“chosen direction”
Blue group – in the
“opposite direction”
Black Arrowheads –
The edges’ “directions”.
Dashed line – spoils
well distribution.
• If both paths’ common edge is in the same
direction we shall put both of them in the same
“group”, else in two different “groups” – The
lack of cycle, assures that the “last” path has to
agree (disagree) with only one “neighbor”
(which is no problem).
So, How Do We Decide On The
“Chosen Direction”
Loop:
• Choose a non-chosen path from S (mark as
chosen).
• If it doesn’t conflict with any chosen path
choose all of the path’s edges’ direction in T
according to the path’s, else if this path
agrees (disagrees) with the conflicting
path’s direction, choose all of the other’s
path’s edges direction according to (against)
the conflicting path’s relative direction.
Deciding On The “Chosen
Direction” - Example
1
2
4
3
Proposition 11 Proof
• There’s only one path between any two vertices in
tree T.
• For any at least four vertices from which every
exactly two “neighbors” conflict, there is at least
one “most close to the beginning vertex” and at
least one “most close to the end vertex”
(“direction”-wise). These two can “complete” a
“conflict cycle”, only if at least one of them
conflicts with all others in the cycle.
• Each “group’s” conflict graph cannot contain
cycles of size > 3 without chords in them.
Proposition 11 Proof
• Each “group’s” conflict graph contains no odd
hole and no odd antihole.
• Each “group’s” conflict graph is perfect.
• cS(T)=S(T). QED
Thanks to:
Prof. Shmuel Zaks and Msc. Mordo Shalom
for their help and guidance.
References
L. Gargano, P. Hell, S. Perennes
“Coloring Paths in Directed Symmetric Trees
with Applications to WDM Routing”, 1997.