Routing Permutations on Trees
Sylvie Corteel
PRISM, Université de Versailles  SaintQuentinenYvelines
Algorithms Seminar
June 19, 2000
[summary by Dominique GouyouBeauchamps]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
Abstract
We study the problem of routing permutations on trees. We show that
this problem is NPhard but that it is 5/3approximable. For a
linear network or for a star tree network, the problem is polynomial
and we give its average complexity. We extend these results and
obtain an upper bound for arbitrary trees. This talk is based on a
joint work with Mario ValenciaPabon, Danièle Gardy, Dominique
Barth, and Alain Denise [4].
1 Introduction
The routing problem on communication networks consists in the
efficient allocation of resources to connection requests. In the case
of alloptical networks, data is transmitted on lightwaves through
optical fiber, and several signals can be transmitted through a fiber
link simultaneously provided that different wavelengths are used in
order to prevent interferences [3]. As the number of
wavelengths is a limited resource, it is desirable to establish a
given set of connection requests with a minimum number of wavelengths.
Then the routing problem for alloptical networks can be viewed as a
path coloring problem: it consists in finding a desirable collection
of paths on the network associated with the collection of connection
requests in order to minimize the number of colors needed to color
these paths in such a way that any two different paths sharing a same
link are assigned different colors. For simple networks, such as
trees, the routing problem is simpler, as there is a unique path for
each communication request.
Clearly, such a routing problem can be modeled as a permutationpath
coloring problem on trees. An instance of the permutationpath
coloring problem on trees is given by a directed symmetric tree
graph T on n nodes and a permutation s of the node set
of T. Moreover, we associate with each pair
(i,s(i)), i¹s(i), 1£ i£ n, the
unique directed path on T from node i to node s(i). Thus,
the permutationpath coloring problem for this instance consists in
assigning the minimum number of colors to such a permutationset of
paths in such a way that any two paths sharing a same arc of the tree
are assigned different colors.
2 Definitions
We model the tree network as a rooted labeled symmetric directed
tree T=(V,A) on n vertices, where processors and switches are
vertices and links are modeled by two arcs in opposite directions.
Let P be a collection of directed paths on T. We assume that the
vertices of T are arbitrarily labeled by different
integers {1,2,...,n} and that the vertex labeled n is the root
vertex of T. We denote i® j the unique directed path from
vertex i to vertex j. The arc from vertex i to its father
(resp. from the father of i to i), 1£ i£ n1, is
labeled by i^{+} (resp. i^{}). We call T(i) the subtree of T
rooted at vertex i, 1£ i£ n.
For any i, 1£ i£ n1, the load of an arc i^{+}
(resp. i^{}) of T, denoted by L_{T}(P,i^{+}) (resp. L_{T}(P,i^{})), is
the number of paths in P using such an arc, and the maximum load
among all arcs of T is denoted by L_{T}(P). We call the coloring
number and we denote by R_{T}(P), the minimum number of colors needed
to color the paths in P such that any two paths sharing a same arc
in T are assigned different colors. Trivially, we have
that R_{T}(P)³ L_{T}(P).
We say that P is a permutationpath set on T if P represents a
permutation sÎ S_{n} of the vertex set of T, where
s(i)=j, i¹ j, if and only if i® jÎ P. In the
sequel we talk indifferently of a permutationpath set P or of the
permutation sÎ S_{n} that P represents. Thus, given a
permutation sÎ S_{n} and a tree T on n vertices, the load
of the arc i^{+}, resp. i^{}, 1£ i£ n1, can be expressed
by L_{T}(s,i^{+})={ jÎ T(i)s (j)Ï
T(i) }, resp. L_{T}(s,i^{})={ jÏ
T(i)s(j)Î T(i) }.
Let T be a tree on n vertices. The average load of all
permutations sÎ S_{n} on T, denoted by L^{_}_{T}, is
defined as L^{_}_{T}=(n!)^{1}å_{sÎ S}_{n}L_{T}(s).
Proposition 1 [[7]]
There is a polynomial time algorithm to color any collection P of
paths on any tree such that L_{T}(P)£
R_{T}(P)£é(5/3)L_{T}(P)ù.
Let T be a tree on n vertices. We denote by R^{_}_{T} the
average number of colors needed to color all permutations in S_{n}
on T.
Proposition 2
Let T be a tree on n vertices.
Then L^{_}_{T}(P)£R^{_}_{T}(P)£(5/3)L^{_}_{T}(P)+1.
Let T be a tree on 2n vertices. We denote by R^{~}_{T} the
average number of colors needed to color all involutions in I_{2n}
on T.
Proposition 3
Let T be a tree on 2n vertices and let L^{~}_{T} be the
average load of all involutions in I_{2n} on T. Then
L^{~}_{T}£R^{~}_{T}£(3/2)L^{~}_{T}.
3 Complexity of Computing the Coloring Number
We show the NPhardness of the symmetricpath coloring problem on
binary trees, answering an open question in [2]. For
this, we use a reduction similar to the one used
in [6, 10] for proving the NPhardness of the general
path coloring problem on binary trees. We extend this reduction to
obtain NPhardness results on very restrictive instances like
involutions on both binary trees and trees having only two vertices
with degrees greater than two.
Theorem 1
Let T be a directed symmetric tree and let P be a collection of
directed paths on T. Then, computing R_{T}(P) is NPhard in the
following cases:

T is a binary tree and P is a collection of symmetric paths
on T.
 T is a binary tree and P represents an involution of the
vertices of T.
 T is a tree with maximum degree greater or equal to 4, and
P represents a circular permutation of the vertices of T.
 T is a tree having only two degrees greater than two and
P represents an involution of the vertices of T.
4 A Lower Bound for the Average Coloring Number
Let G=(V,A) be a directed symmetric graph on n vertices and r a
routing function in G which assigns a set of paths on G to route
any permutation sÎ S_{n}. Let L^{_}_{G,r} be the average
load of all permutations in S_{n} induced by the routing function r,
and let UÍ V be a subset of the vertex set of G. We
denote by c(U) the cut (U,U^{_}), i.e., the set of arcs
{ (u,v)Î A uÎ U, vÎ V\ U }.
Proposition 4
For any graph G=(V,A) on n vertices, and any routing function r
in G,
Let T be a tree on n vertices. By the previous proposition, we
can deduce that the average load of any arc i^{+} of T, 1£
i£ n1, denoted by L^{_}_{T}(i), satisfies
L^{_}_{T}(i)=T(i)(nT(i))/n. Moreover, for any
vertex i of T, let v_{T}(i)=T(i)/n
and v^{~}_{T}(i)=min(v_{T}(i),1v_{T}(i)).
Let v^{~}_{T}=max_{i}v^{~}_{T}(i).
Proposition 5
Both inequalities L^{_}_{T}³ nv^{~}_{T}(1v^{~}_{T})
and R^{_}_{T}³ nv^{~}_{T}(1v^{~}_{T}) hold.
5 Average Coloring Number on Linear Networks
The main result is the following:
Theorem 2
The average coloring number of the permutations in S_{n} to be routed
on a linear network on n vertices
is n/4+(l/2)n^{1/3}+O(n^{1/6}) where l=0.99615...
To prove this result, we use enumerative and asymptotic combinatorial
techniques (Theorems 3 and 4 below and results of
Louchard [12] and Daniels and Skyrme [5]). Our
approach uses the same methodology as Lagarias et al. [11]
who studied involutions with no fixed point routed on the linear
network.
Let W_{n} be the set of Motzkin walks of length n labeled as
follows:

each SouthEast step of height i is labeled by an integer
between 1 and (i+1)^{2},
 each East step of height i is labeled by an integer between 1
and 2i+1.
Theorem 3 [9]
There is a onetoone correspondence between the elements W_{n} and
those of S_{n}.
We use Biane's bijection [1] because it preserves the
height of our objects, i.e., the height of a labeled Motzkin walks is
equal to the height of the corresponding permutation. Moreover, the
height of a permutation is equal to its load.
Let S_{n,£ k} be the number of permutations in S_{n} of height at
most k and let S_{n,k} be the number of permutations in S_{n} of
height exactly k.
Theorem 4 [8, 13]
We have the identities H_{k}(z)=å_{n³
0}å_{sÎ S}_{n,k}z^{n}
=(k!)^{2}z^{2k}/P_{k+1}^{*}(z)P_{k}^{*}(z) and
with P_{0}(z)=1, P_{1}(z)=z1
and P_{n+1}(z)=(z2n1)P_{n}(z)n^{2}P_{n1}(z) for n³ 1, where
P^{*} is the reciprocal polynomial of P, that is
P_{n}^{*}(z)=z^{n}P_{n}(1/z) for n³ 0.
6 Average Coloring Number on Arbitrary Tree Networks
We can extend the average complexity results on linear networks to
arbitrary tree networks.
Theorem 5
The average load induced by all permutations of S_{n} on T
is L^{_}_{T}=nv^{~}_{T}(1v^{~}_{T})+O(n^{1/2}).
Theorem 6
For all e, there exists n_{0}=n_{0}(e) such that, for
all n³ n_{0} and any tree T on n vertices, the average number
of colors R^{_}_{T} needed to color any permutation sÎ S_{n}
on T satisfies
R^{_}_{T}£(5/3+e)nv^{~}_{T}(1v^{~}_{T}).
Let ST(n) denote the directed symmetric star graph on n vertices
(i.e., the tree having only one internal vertex connected to n1
leaves). We call generalized star graph that we denote
by GST(l), a directed symmetric tree on n vertices
having k branches connected to each other by one vertex, where
l=(l_{1},...,l_{k}) is a partition of the
integer n1 into k parts (k>2) and where l_{i} denotes the
length of the ith branch (i.e., a branch of length l_{i} is a
path graph on l_{i}+1 vertices). We can also obtain the same
type of results for generalized star trees and involutions instead of
permutations.
Theorem 7
Let k be a fixed integer greater than 2. The average number of
colors needed to color any permutation sÎ S_{nk+1} on a
generalized star tree GST(l) having nk+1 vertices and
k branches of length n is n(k1)/k+O(n^{1/2}).
Theorem 8
Let T be a tree on 2n vertices. The average load induced by all
involutions with no fixed points sÎ I_{2n} on T
is L^{_}_{T}=2nv^{~}_{T}(1v^{~}_{T})+O(n^{1/2}).
References
 [1]

Biane (Philippe). 
Permutations suivant le type d'excédance et le nombre d'inversions
et interprétation combinatoire d'une fraction continue de Heine. European Journal of Combinatorics, vol. 14, n°4, 1993,
pp. 277284.
 [2]

Caragiannis (I.), Kaklamanis (C.), and Persiano (P.). 
Wavelength routing of symmetric communication requests in directed
fiber trees. In Proceedings of SIROCCO'98, pp. 221222. 
1998.
 [3]

Cheung (N. K.), Nosu (K.), and Winzer (G.) (editors). 
Dense wavelength division multiplexing techniques for high
capacity and multiple access communication systems. 
vol. 8, August 1990. Special issue of IEEE
Journal on Selected Areas in Communications.
 [4]

Corteel (S.), ValenciaPabon (M.), Gardy (D.), Barth (D.), and Denise (A.). 
The permutationpath coloring problem on trees. 
Rapport de recherche du LRI n°1256, Université de Paris Sud,
2000.
 [5]

Daniels (H. E.) and Skyrme (T. H. R.). 
The maximum of a random walk whose mean path has a maximum. Advances in Applied Probability, vol. 17, n°1, 1985,
pp. 8599.
 [6]

Erlebach (T.) and Jansen (K.). 
Call scheduling in trees, rings and meshes. In Proceedings of
the 30th Hawaii International Conference on System Sciences HICSS30. 
IEEE CS Press, 1997.
 [7]

Erlebach (Thomas), Jansen (Klaus), Kaklamanis (Christos), Mihail (Milena), and
Persiano (Pino). 
Optimal wavelength routing on directed fiber trees. Theoretical
Computer Science, vol. 221, n°12, 1999, pp. 119137. 
Proceedings of ICALP '97 (Bologna).
 [8]

Flajolet (P.). 
Combinatorial aspects of continued fractions. Discrete
Mathematics, vol. 32, n°2, 1980, pp. 125161.
 [9]

Françon (Jean) and Viennot (Gérard). 
Permutations selon leurs pics, creux, doubles montées et double
descentes, nombres d'Euler et nombres de Genocchi. Discrete
Mathematics, vol. 28, n°1, 1979, pp. 2135.
 [10]

Kumar (S. Ravi), Panigrahy (Rina), Russell (Alexander), and Sundaram (Ravi). 
A note on optical routing on trees. Information Processing
Letters, vol. 62, n°6, 1997, pp. 295300.
 [11]

Lagarias (J. C.), Odlyzko (A. M.), and Zagier (D. B.). 
On the capacity of disjointly shared networks. Computer Networks
and ISDN Systems, vol. 10, n°5, 1985, pp. 275285.
 [12]

Louchard (G.). 
Random walks, Gaussian processes and list structures. Theoretical Computer Science, vol. 53, n°1, 1987,
pp. 99124.
 [13]

Viennot (Gérard). 
A combinatorial theory for general orthogonal polynomials with
extensions and applications. In Orthogonal polynomials and applications
(BarleDuc, 1984), pp. 139157. 
Springer, Berlin, 1985. n°1171 in Lecture Notes in
Mathematics.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.