Routing Permutations on Trees

Sylvie Corteel

PRISM, Université de Versailles - Saint-Quentin-en-Yvelines

Algorithms Seminar

June 19, 2000

[summary by Dominique Gouyou-Beauchamps]

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 NP-hard but that it is 5/3-approximable. 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 Valencia-Pabon, 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 all-optical 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 all-optical 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 permutation-path coloring problem on trees. An instance of the permutation-path 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 permutation-path coloring problem for this instance consists in assigning the minimum number of colors to such a permutation-set 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£ n-1, 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£ n-1, the load of an arc i+ (resp. i-) of T, denoted by LT(P,i+) (resp. LT(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 LT(P). We call the coloring number and we denote by RT(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 RT(P)³ LT(P).

We say that P is a permutation-path set on T if P represents a permutation sÎ Sn 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 permutation-path set P or of the permutation sÎ Sn that P represents. Thus, given a permutation sÎ Sn and a tree T on n vertices, the load of the arc i+, resp. i-, 1£ i£ n-1, can be expressed by LT(s,i+)=|{ jÎ T(i)|s (j)Ï T(i) }|, resp. LT(s,i-)=|{ jÏ T(i)|s(j)Î T(i) }|.

Let T be a tree on n vertices. The average load of all permutations sÎ Sn on T, denoted by L_T, is defined as L_T=(n!)-1åsÎ SnLT(s).

Proposition 1  [[7]]   There is a polynomial time algorithm to color any collection P of paths on any tree such that LT(P)£ RT(P)£é(5/3)LT(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 Sn 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 I2n on T.

Proposition 3   Let T be a tree on 2n vertices and let L~T be the average load of all involutions in I2n on T. Then L~T£R~T£(3/2)L~T.

3   Complexity of Computing the Coloring Number

We show the NP-hardness of the symmetric-path 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 NP-hardness of the general path coloring problem on binary trees. We extend this reduction to obtain NP-hardness 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 RT(P) is NP-hard in the following cases:

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Î Sn. Let L_G,r be the average load of all permutations in Sn 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,
_
L
 
G,r³
1
n
 
max
UÍ V
æ
ç
ç
è
|U|(n-|U|)
|c(U)|
ö
÷
÷
ø
.

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£ n-1, denoted by L_T(i), satisfies L_T(i)=|T(i)|(n-|T(i)|)/n. Moreover, for any vertex i of T, let vT(i)=|T(i)|/n and v~T(i)=min(vT(i),1-vT(i)). Let v~T=maxiv~T(i).

Proposition 5   Both inequalities L_T³ nv~T(1-v~T) and R_T³ nv~T(1-v~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 Sn to be routed on a linear network on n vertices is n/4+(l/2)n1/3+O(n1/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 Wn be the set of Motzkin walks of length n labeled as follows:
Theorem 3  [9] There is a one-to-one correspondence between the elements Wn and those of Sn.

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 Sn,£ k be the number of permutations in Sn of height at most k and let Sn,k be the number of permutations in Sn of height exactly k.

Theorem 4  [8, 13] We have the identities Hk(z)=ån³ 0åsÎ Sn,kzn =(k!)2z2k/Pk+1*(z)Pk*(z) and
H
 
£ k
(z)=
 
å
n³ 0
 
å
sÎ S
 
n,£ k
zn=
1
1-
z2
1-3z-
4z2
1-5z-
·
·
·
1-(2k-1)z-
k2z2
1-(2k+1)z
,
with P0(z)=1, P1(z)=z-1 and Pn+1(z)=(z-2n-1)Pn(z)-n2Pn-1(z) for n³ 1, where P* is the reciprocal polynomial of P, that is Pn*(z)=znPn(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 Sn on T is L_T=nv~T(1-v~T)+O(n1/2).

Theorem 6   For all e, there exists n0=n0(e) such that, for all n³ n0 and any tree T on n vertices, the average number of colors R_T needed to color any permutation sÎ Sn on T satisfies R_T£(5/3+e)nv~T(1-v~T).

Let ST(n) denote the directed symmetric star graph on n vertices (i.e., the tree having only one internal vertex connected to n-1 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=(l1,...,lk) is a partition of the integer n-1 into k parts (k>2) and where li denotes the length of the ith branch (i.e., a branch of length li is a path graph on li+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Î Snk+1 on a generalized star tree GST(l) having nk+1 vertices and k branches of length n is n(k-1)/k+O(n1/2).

Theorem 8   Let T be a tree on 2n vertices. The average load induced by all involutions with no fixed points sÎ I2n on T is L_T=2nv~T(1-v~T)+O(n1/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. 277--284.

[2]
Caragiannis (I.), Kaklamanis (C.), and Persiano (P.). -- Wavelength routing of symmetric communication requests in directed fiber trees. In Proceedings of SIROCCO'98, pp. 221--222. -- 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.), Valencia-Pabon (M.), Gardy (D.), Barth (D.), and Denise (A.). -- The permutation-path 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. 85--99.

[6]
Erlebach (T.) and Jansen (K.). -- Call scheduling in trees, rings and meshes. In Proceedings of the 30th Hawaii International Conference on System Sciences HICSS-30. -- 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°1-2, 1999, pp. 119--137. -- Proceedings of ICALP '97 (Bologna).

[8]
Flajolet (P.). -- Combinatorial aspects of continued fractions. Discrete Mathematics, vol. 32, n°2, 1980, pp. 125--161.

[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. 21--35.

[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. 295--300.

[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. 275--285.

[12]
Louchard (G.). -- Random walks, Gaussimeanrocesstches areEast ructures. Theoretical Computer Science, vol. 53, n°1, 1987, pp. 99--124.

[13]
Viennot (Gérard). -- A combinatorial theory for general orthogonal polynomials with extensions and applications. In Orthogonal polynomials and applications (Bar-le-Duc, 1984), pp. 139--157. -- Springer, Berlin, 1985. n°1171 in Lecture Notes in Mathematics.

This document was translated from LATEX by HEVEA.