Routing Permutations on Trees

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 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 permutation-path 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 permutation-path 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£ n-1, 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 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 R_T(P) is NP-hard 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,

_G,r³

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 v_T(i)=|T(i)|/n and v^~_T(i)=min(v_T(i),1-v_T(i)). Let v^~_T=max_iv^~_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 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 South-East step of height i is labeled by an integer between 1 and (i+1)²,
each East step of height i is labeled by an integer between 1 and 2i+1.

Theorem 3 [9] There is a one-to-one 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ⁿ =(k!)²z^2k/P_k+1^*(z)P_k^*(z) and

£ k

(z)=

n³ 0

sÎ S

n,£ k

zⁿ=

z²

1-3z-

4z²

1-5z-

·
·
·

1-(2k-1)z-

k²z²

1-(2k+1)z

with P₀(z)=1, P₁(z)=z-1 and P_n+1(z)=(z-2n-1)P_n(z)-n²P_n-1(z) for n³ 1, where P^* is the reciprocal polynomial of P, that is P_n^*(z)=zⁿ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(1-v^~_T)+O(n^1/2).

Theorem 6 For all e, there exists n₀=n₀(e) such that, for all n³ n₀ 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(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=(l₁,...,l_k) is a partition of the integer n-1 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(k-1)/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(1-v^~_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. 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, Gaussian processes and list structures. 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 L^AT_EX by H^EV^EA.