Minimum Moment Steiner Trees Wangqi Qiu Weiping Shi a rectilinear Steiner tree for P that has the shortest total edge length. A rectilinear Steiner arborescence [5, 8] for P is a rectilinear Steiner tree for P such that For a rectilinear Steiner tree T with a root, define its for each pi P , the length of the unique path in the k -th moment tree from root p0 to pi is pi . A rectilinear Steiner T Minimum Arborescence (SMA) for P is a rectilinear Mk (T ) = (dT (u))k du, Steiner arborescence for P that has the shortest total edge length. where the integration is over all edges of T , dT (u) is Since the whole paper is about rectilinear Steiner the length of the unique path in T from the root to trees, we omit the word "rectilinear" in the rest of the u, and du is the incremental edge length. Given a set of points P in the plane, a k -th moment Steiner paper. Minimum Tree (k -SMT) is a rectilinear Steiner tree that has the minimum k -th moment among all recti- Definition 1.1 For a Steiner tree T with a root, delinear Steiner trees for P , with the origin as the root. fine its k -th moment: T The definition is a natural extension of the traditional Mk (T ) = (dT (u))k du, Steiner minimum tree, and motivated by application in VLSI routing. In this paper properties of the k SMT are studied and approximation algorithms are where the integration is over al l edges of T , dT (u) is the length of the unique path in T from the root to presented. u, and du is the incremental edge length. Given a set of points P in the plane, a k -th moment Steiner Minimum Tree (k -SMT) is a Steiner tree that has the 1 Intro duction minimum k -th moment among al l Steiner trees for P , with the origin as the root. Abstract We are given a set of points P = {p0 , p1 , . . . , pn } in Clearly, 0-SMT is the traditional SMT. Figure 1 the plane, where p0 = (0, 0), pi = (xi , yi ), and xi , yi shows the SMT, 1-SMT and SMA for a set of points. are integers. An edge is a horizontal or vertical line segment. A rectilinear tree is a connected acyclic col- M0 (T1 ) = 14, M0 (T2 ) = 15, M0 (T3 ) = 16, M1 (T1 ) = lection of edges, which intersect only at the endpoints, 98, M1 (T2 ) = 97.5, and M1 (T3 ) = 98. which we call nodes. We use pi = |xi | + |yi | to represent the rectilinear distance between p0 and pi . r r r1 1 1 2r 1 r r 1 T2 T3 2 2 T1 2 2 A rectilinear Steiner tree [2, 4] for P is a rectilinear r r r 1 2 tree such that each point pi P is a node in the tree. 2 2 2 r r r r p0 r 5 p0 r 6 1 2 7 A rectilinear Steiner Minimum Tree (SMT) for P is p0 This research was supp orted in part by NSF grants CCR0098329, CCR-0113668, EIA-0223785, and ATP grant 5120266-2001. Department of Computer Science, Texas A&M University, College Station, Texas 77843. Email: wangqiq@cs.tamu.edu Department of Electrical Engineering, Texas A&M University, College Station, Texas 77843. Email: wshi@ee.tamu.edu Figure 1: T1 is an SMT, T2 is a 1-SMT, and T3 is an SMA. The new formulation is motivated by the advances in Very Large Scale Integration (VLSI). As the feature size of integrated circuits reduces, the wire delay Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688 488 estimation based the total wire length is no longer accurate. In 1983, Rubinstein, Penfield and Horowitz [7] proposed to use the first moment of the routing tree, also known as the Elmore delay, to estimate the wire delay. In 1993, Cong, Leung and Zhou [1] defined quadratic Steiner tree, which is our 1-SMT. However, there has been no study on the properties of k -SMT for any k 1, nor any approximation algorithm. This paper contains the following results: · For any constant k 1, k -SMT is NP-hard, but not known in NP. · For any constant k 1, the k -th moment of an SMT can be a factor of (nk/2 ) worse than that of a k -SMT, and the k -th moment of an SMA can be a factor of (log n) worse than that of a k -SMT. · Given P , it is obvious any 0-SMT for P is an SMT. Any -SMT for P is a Steiner arborescence. s p0 W = 2 k L4 L 6 L ? - spi P Figure 2: Construction used for reduction. If M0 (T ) < M0 (T ), then Mk (T {(p0 , pi )}) - Mk (T {(p0 , pi )}) M0 (T )(W + L2 )k - M0 (T )W k (M0 (T ) - 1)(W + L2 )k - M0 (T )W k M0 (T )((W + L2 )k - W k ) - (W + L2 )k L2 (2k L2 W k-1 ) - (W + L2 )k W k - (W + L2 )k 0. < = < = < It is not known if the k -SMT problem is in NP, since · An (8/3)c-approximation algorithm for the 1the k -SMT problem does not have the Hanan property SMT problem, where c 1 + ln 3/2 is the per- as shown below. formance for the approximation of Steiner trees in graphs. Definition 2.1 The Hanan grid of a set of points P · An f (k )-approximation algorithm for the k -SMT is the grid G(P ) that includes a vertical line and a problem, where f (k ) is a function of k but inde- horizontal line through every point pi P . A problem has Hanan property if there exists an optimal solution pendent of n. that uses only edges of G(P ). 2 Prop erties Theorem 2.1 The k -SMT problem is NP-hard for any constant k 0. Pro of. For k = 0, the problem is the same as the SMT problem, a well known NP-Complete problem [2]. For k 1, we use a reduction from SMT. Given an instance P for the SMT problem, let the leftmost point of P be pi = (xi , yi ). Let the minimum square that contains P be size L × L. Define the new root p0 = (xi - W, yi ), where W = 2k L4 , see Figure 2. Now we show for any Steiner trees T and T of P , M0 (T ) < M0 (T ) if and only if Mk (T {(p0 , pi )}) < Mk (T {(p0 , pi )}). Hanan property is useful since it reduces the solution space and makes the problem in NP. Both the SMT problem and the SMA problem have Hanan property [3, 5]. Theorem 2.2 The k -SMT problem does not have Hanan property for any k 1. Pro of. In Figure 1, the 1-SMT does not use edges of G(P ). Similar examples can be constructed for general k . In general, the solutions are not rational. Theorem 2.3 For any constant k 1, let TS M T (P ) be an SMT for P and Tk-S M T (P ) be a k -SMT for P . 489 Then max P Mk (TS M T (P )) = (nk/2 ). Mk (Tk-S M T (P )) pn s s 6 s s s s s n-1 Prof. In Figure 3, there are n points placed in o ( n) rows, with ( n) points on each odd row, and 1 point on each even row. It was shown the length of TS M A for the right half is size Then it is easy to see n , Mk (TS M T (P )) = k+1 n Mk (TS M A (P )) = k/2+1 s s s s s s s p0 s ? n - TS M A pn s s s n-1 s - s p1 . s s s pn s s s s s s s s6 sssssss s ( n) sssssss s1 1 s p0 s 1 s 1 s s s s ? ( n) TS M T pn s s s s s s s s sssssss s sssssss s 2 s s s s s s s1 p0 1 1 TS M A s s s s s s s s p0 s s TS M T s p1 Figure 4: SMA is not a good approximation for k SMT. Pro of. Let (s, t) be any non-monotone path of length > 0 without branch in a k -SMT. By non-monotone, we mean the path from the root to t goes through s, and s > t . We show there exists a K = K ( ) such that when k > K , such non-monotone path can not exist in any k -SMT. The k -th moment of path (s, t) is dT (t) dT (s) Figure 3: SMT is not a good approximation for k SMT. Theorem 2.4 For any constant k 1, let TS M A (P ) be an SMA for P and Tk-S M T (P ) be a k -SMT for P . Then max P Mk (TS M A (P )) = (log n). Mk (Tk-S M T (P )) s u du k s + uk du uk du k+1 Pro of. In Figure 4, there are n points equally spaced on the diagonal line from p1 to pn . It was shown in [5] that the total edge length for the right half of TS M A is (n log n). Therefore, it is easy to verify Mk (TS M A ) = (nk+1 log n), Mk (TS M T ) = (nk+1 ). t + > t > = ( 1 t + )k+1 - t k+1 · t k. On the other hand, a direct path from the root to t will have k -th moment t k+1 /(k + 1). Therefore when k K = t / - 1, we have t /(k + 1) and Theorem 2.5 For any P , limk k -SMT(P ) is a Steiner arborescence. ·t k 1 t k+1 k+1 . 490 That means a direct path (p0 , t) will have less k th moment than the (s, t) path. Therefore such (s, t) path cannot exist in any k -SMT. Even though an -SMT must be a Steiner arborescence, an -SMT is not necessarily an SMA, see Figure 5. 3 1 Pro of. Mk (Tk-S M T (P )) Dk (Tk-S M T (P )) Dk (Tk-DM T ). Lemma 3.2 The k -DMT problem has Hanan property. Pro of. We prove that for any set of points P , there exists a k -DMT that uses only edges of G(P ). The proof is an adaptation of Hanan's proof for rectilinear Steiner tree problem [3]. Suppose we have a k -DMT T for P , and a grid G(P ). Let I be the set of intersection points on G(P ). Let Q be the set of nodes of T that are not in I . Points in Q are either Steiner points with degree 3 or 4, or corner points with degree 2. Let I-point denote a point in I and Q-point a point in Q. In the following we will show all Q-points of T can be removed to obtain a new tree T such that Dk (T ) = Dk (T ). For any Q-point s, let NI (s) be the number neighbors of s that are in I . Let d(s) be the degree of point s. Table 1 shows the cases. s s s 3 s 5 6 s 3 5 s s p0 s s 5 1 p0 s 5 SMA -SMT Figure 5: An SMA is not necessarily an -SMT. 3 Approximation Algorithm For any edge e, Mk (e) depends on the path from root to e. Therefore, any change in one part of the tree For Case 1, it is easy to see s I . affects the k -th moment in other parts of the tree. This makes it difficult to apply most approximation For Case 2, if s is a Steiner point and d(s) = 4, s techniques on the k -SMT problem for any k 1. In can be seen as 2 Steiner points s1 and s2 , and d(s1 ) = the following, we introduce another cost function that d(s2 ) = 3. Therefore we only need to consider d(s) = is closely related to Mk , but is independent of the rest 3. of the tree. s i1 i2 Definition 3.1 For any Steiner tree T , define the k t1 . . th direct cost s s . i1 i2 t i1 i2 T qi i k Dk (T ) = u du, qj tj t1 . q1 q1 . . where u =| xu | + | yu | is the rectilinear distance tm qm from the origin to u. For a given set of points P and the origin as the root, a rectilinear k -th Direct (a) (c) (b) Cost Steiner Minimum Tree (k -DMT) is a rectilinear Steiner tree T such that Dk (T ) is the minimum among Figure 6: Case 2, where s Q, d(s) = 3, N (s) = 2. I al l rectilinear Steiner trees for P . Let the 2 neighboring I-points of s be i1 and i2 , Lemma 3.1 For any P , let Tk-S M T (P ) be a k -SMT and the 1 neighboring Q-point be q . Without loss of 1 for P and Tk-DM T be a k -DMT for P . Then generality, we can assume that i1 is on the left of s, i2 is on the right of s, and q1 is below s, see Figure Mk (Tk-S M T (P )) Dk (Tk-DM T (P )). 6(a). If i1 is on the left of s and i2 is below s, then clearly s I . Furthermore, assume the X-coordinate 491 Table 1: Cases in proving Hanan property for k -DMT. NI (s) 2 Case 1 Case 2 Case 2 d(s) 2 3 4 0 Case 4 Case 4 Case 4 1 Case 3 Case 4 Case 4 3 / Case 1 Case 1 4 / / Case 1 tioq to the factq that T is a 1-DMT. If ( sqm + n qi - qj ) < 0, then for any < 0, i L j R ) D1 (T ) - D1 (T > 0, again a contradiction. If we follow the edge sq1 downward, we might find q q some edges qi ti going left, and some edges qj tj going If ( sqm + qi - qj ) = 0, and r - i L j R right, and qi 's and qj 's may overlap, see Figure 6(b). l > 0, then D1 (T ) - D1 (T ) > 0 for any = 0. Note that q1 t1 must go right, since otherwise we will be q q Finally, if ( sqm + qi - qj ) = 0, in Figure 6(c), and by moving edge sq1 to left we can i L j R reduce the cost. Let qm be the end of the sequence of and r - l = 0, then D1 (T ) - D1 (T ) = 0 for any . edges from s that are on the same vertical line. Edge When this happens, we can move all edges from s to qm tm may go either left or right. Let L = {qi | qi ti qm to the left or right, to either make s an I-point, or goes to left}, R = {qj | qj tj goes to right}, l = |L| and remove another Q-point. r = |R|. For k 2, we prove that T is not a k -DMT by Move all vertical edges from s to qm to left by , and contradiction. correspondingly, increase the length of edges going to For the time being, assume qm is also in the first right and decreasing the length of edges going to left. quadrant. Let . Call the new tree T ( ) = Dk (T ) - Dk (T ) First consider the case k = 1. s- qs k ) = du - uk du D1 (T ) - D1 (T of s is greater than 0. Otherwise, reflect the graph about Y -axis. = ( sqm ) · + = ( sqm ) · + = sqm + q i L q i L q qi udu - i q j R q qj m u udu j - - + q i L q qi i qm - u du - - k q j R q qj j uk du. - q i L 2 qi 2 q -2 qi - - 2 Since T is a k -SMT, ( ) reaches local maximum at k - 2 = 0. Therefore j R q q d = s k+ qi k - qj k - qm k (r - l ) 2 d =0 qj + . i L j R q 2 qj j R = 0, = k q j R For every i, if qi ti goes to left, qi+1 ti+1 must go to and right, otherwise moving edge qi qi+1 to left will reduce = d2 the cost, which is a contradiction to the fact that T d2 is a 1-DMT. Therefore, r - l 0 except for one case, 0 which is in Figure 6(c) (but clearly in this case moving edge sq1 to left reduces the cost). q q If ( sqm + qi - qj ) > 0, then i L j R for any > 0, D1 (T ) - D1 (T ) > 0, contradic- qj k-1 + qm k-1 k-1 -k s 0. + q i L qi k - 1 492 Let s = q0 and L = L {q0 }. Let qm = qm and R = R {qm }. Since q q i k= j k, i L q j R q and the property that s q1 · · · qm , it can be shown that there exist lr positive real numbers i,j such that for each qj R , i i,j = 1, and for each qi L , 3 from Q. Assume the contrary, that is, if Q is not empty, any point s remaining in Q is either d(s) 3 and NI (s) 1, or d(s) = 2 and NI (s) = 0. It implies that for any s in Q, there are at least 2 edges, each connects s with another Q-point. Suppose there are m such points remaining in Q. It's easy to see that for the subgraph with those m points, there are at least m edges in this subgraph. This implies that there exists a cycle in this subgraph. Obviously it cannot happen. Therefore, Q is empty. Given a graph G = (V , E ) with weight w : E [0, +) and a subset of vertices S V , a Steiner tree q T for S is a connected subgraph that contains all the e qi k = i,j qj k, vertices in S and T w (e) is minimum. Finding j R Steiner tree for graphs is NP-Complete. The best apwhere i,j = 0 for qj > qi . Such i,j 's must proximation algorithm is a factor of 1 + ln 3/2 from exist, since otherwise, we would be able to move edges the optimal [6]. between s and qj , for some qj R , to the right to For each edge e of Hanan grid G(P ), assign weight reduce the k -th directed cost of T . Then, we have w(e) = Dk (e). Lemma 3.2 says that in order to find q a k -DMT, we can find an SMT for graph G(P ) with qi k-1 < = i,j qj k/ qi weight w. q j R i,j j R qj k-1 . Therefore, q i Our approximation algorithm is given in Figure 7. At step 7 of the algorithm, the factor 3 is from careful analysis for k = 1 in order to give the best performance bound. Let v1 , v2 , . . . , vm be the nodes to which the algorithm adds direct paths from the root p0 . Let q q i L j R R1 , . . . , Rm+1 be the depth-first traversal of Td , where 2 which contradicts with the fact that (d /d 2) | =0 Ri is between vi-1 and vi . Let L1 , . . . , Lm be the paths added, where Li is from p0 to vi . Figure 8 shows one 0. part of the graph generated by the above algorithm. If qm is in the fourth quadrant, then either d(qm ) = In the figure, Ri is the traversal path from vi-1 to vi . 3 or qm tm goes to right, otherwise we can flip the There may be some nodes in the path. When Li is qm corner from shape " " to shape " " to reduce the added, the length of the path from p0 through vi-1 to direct cost. Thus, we can divide the subgraph into vi is 3 vi , or (| Li-1 | + | Ri |) = 3 vi = 3 | Li |. two parts, one in the first quadrant and the other in the fourth quadrant, then we get similar cases, which Lemma 3.3 In step 10 of the algorithm when Li is will also lead to a contradiction. 8 added, M1 (Li-1 ) + M1 (Ri ) + M1 (Li ) 3 D1 (Ri ). Case 3. Now consider the case that s is a corner point d(s) = 2 and NI (s) = 1. This case can be Pro of. Paths Li-1 , Li and Ri form a cycle of length viewed as a special case of Figure 6(a), by removing point i1 and edge si1 , or removing point i2 and edge |Li-1 | + |Ri | + |Li | = 4|Li |. si2 . Then a similar argument shows s can be removed from Q. Therefore, Case 4. The following argument proves that Q is empty after removing all s that are in Cases 1, 2 and M1 (Li-1 ) + M1 (Ri ) + M1 (Li ) k -1 < j q k -1 , 493 Algorithm 1 Approximation algorithm for 1-SMT. Input: P = {p1 , . . . , pn } is a set of points and root p0 = (0, 0). Output: T is an approximation 1-SMT. 1: Construct G(P ) and assign weight w(e) = D1 (e) for each edge e; 2: Find Steiner minimum tree Td for P in graph G(P ); 3: Traverse edges of Td in depth-first order; Let e1 , e2 , . . . , eN be the sequence of edges of Td in the traversal, where each edge appears twice; 4: Let i 1, T ; 5: while i N do b egin 6: Consider edge ei = (ui , ui+1 ); 7: if dT (ui ) + (ui , ui+1 ) < 3 ui+1 then 8: T T {ei }, i i + 1; 9: else find point q ei such that dT (ui ) + (ui , q ) = 3 q ; 10: T T {(p0 , q ), (q , ui )}, ui q ; 11: end; 12: for each pi P do 13: Mark the edges of T on the shortest path from pi to p0 ; 14: Delete all edges that are not marked. Figure 7: Approximation algorithm for 1-SMT. 2 |Li-1 | 1 Ri vi s sp Li p0 s x Traversal direction vi-1 s Li-1 0 (| Li-1 | -x)dx | Li-1 | +x dx 3 3|Li |-|Li-1 | 1 2 |Li-1 | + = 3 2 | Li | . 2 Figure 8: Part of depth-first traversal R, with direct paths added. 2|Li | =2· 0 2 udu = 4|Li | . Theorem 3.4 Given a set of points, Algorithm 1 finds a Steiner tree T in polynomial time such that M1 (T ) 8 c · M1 (T1-S M T (P )), where c is the factor 3 for best approximation algorithm for Steiner trees in graphs, and T1-S M T (P ) is a 1-SMT for P . Pro of. The time complexity is bounded by the time to find Steiner trees for graphs in step 2 of the algorithm. All other steps are low order polynomial. On the other hand, consider any point p on Ri . Let the length of path from vi-1 to p be x. Then from the algorithm, the length of path (p0 , p) through vi-1 is at most 3 p . In addition, p |Li-1 | - x. Therefore, u D1 (Ri ) = u du |Ri | 0 Ri | max Li-1 | +x , | Li-1 3 Suppose we have found Td which is a capproximation 1-DMT. Let v1 , v2 , . . . , vm be the nodes to which the algorithm adds direct paths from the root d p0 . Let R1 , . . . , Rm+1 be the depth-first traversal of | -x x T , where R is between v d i i-1 and vi . Let L1 , . . . , Lm 494 be the paths added, where Li is from p0 to vi . For any point u Td , there are 2 corresponding copies u , u n R = {R1 , . . . , Rm+1 }, because the traversal goes a through u twice. Suppose u appears in Rj and u ppears in Rk , and dT (u ) is the length from the root p0 to u through Rj and dT (u ) the length through Rk . Because in step 14, we keep the shortest path from p0 to u, i References [1] J. Cong, K. S. Leung, and D. Zhou, Performance driven interconnect design based on distributed RC delay model, in Proc. 30th Design Automation Conf., June 1993, pp. 606­611. [2] M. R. Garey and D. S. Johnson, The rectilinear Steiner tree problem is NP-complete, SIAM J. Appl. Math. 32 (1977), pp. 826­834. [3] M. Hanan, On Steiner's problem with rectilinear distance, SIAM J. Appl. Math. 14 (2) (1966), pp. 255­265. dT (u) = min{dT (u ), dT (u )} Therefore, M1 (T ) = im =1 dT (u ) + dT (u 2 ) . u M 1 ( Li ) + Td dT (u ) + dT (u 2 ) du im =1 M 1 ( Li ) + m+1 1i M1 (Ri ) 2 =1 [4] F. K. Hwang, D. S. Richards, and P. Winter, The Steiner Tree Problem, North-Holland, Amsterdam, 1992. [5] S. K. Rao, P. Sadayappan, F. K. Hwang, and P. W. Shor, The rectilinear Steiner arborescence problem, Algorithmica 7 (1992), pp. 277­288. [6] G. Robins and A. Zelikovsky, Improved Steiner tree approximation in graphs, in Proc. 11th ACM-SIAM Symp. Disc. Algo. (SODA), Jan. 2000, pp. 770­779. [7] J. Rubinstein, P. Penfield, Jr., and M. Horowitz, Signal delay in RC tree networks, IEEE Trans. on Computer-Aided Design 2 (3) (1983), pp. 202­ 211. [8] W. Shi and C. Su, The rectilinear Steiner arborescence problem is NP-complete, in Proc. 11th ACM-SIAM Symp. Disc. Algo. (SODA), Jan. 2000, pp. 780­787. m+1 1i (M1 (Li-1 ) + M1 (Ri ) + M1 (Li )). 2 =1 Here, we let M1 (L0 ) = M1 (Lm+1 ) = 0 to satisfy the boundary condition. From Lemma 3.3, M1 (T ) m+1 1i 8 4 8 D1 (Ri ) · 2D1 (Td ) = D1 (Td ). 2 =1 3 3 3 On the other hand, let T be optimal Steiner tree for G(P ), then from Lemma 3.1, D1 (Td ) c · D1 (T ) c · M1 (T1-S M T ). Therefore, M1 (T ) 8 c · M1 (T1-S M T ). 3 Because the Hanan property is true for k -DMT, we have Theorem 3.5 Algorithm 1 works for any k , except that the constant 3 in steps 7 and 9 has to be changed to k = 2(k+1)/k - 1. The performance is bounded by f (k ) = (k + 1)k+1 c, k 2k where c 1 + ln 3/2 is the performance for the approximation of Steiner trees in graphs. 495