Carmerini - A Note On Finding Optimum Branchings

A Note on Finding Optimum Branchings P. M. Camerini L. Fratta F. Maffioli Centro Studi per le Telecomunicazioni Spaziali of CNR and lstituto di Elettrotecnica ed Elettronica, Politechnico di Milano, Milano, Italy

ABSTRACT

The subject of t h i s note i s Tarjan's aZgorithm for finding an optimum branching in a directed graph. !Two errors are pointed out, namely (i) an incorrect cZaim invoZving branching uniqueness, and (ii) an imprecise way of updating edge vaZues i n each i t e r a t i o n . These two inaccuracies do not a f f e c t the basic v a l i d i t y of the algorithm. I t is s h m here t h a t they may be f i x e d v i a a simpZe modification, which Zeaves unchanged the overall time and space performances. I n t h e paper on "Finding Optimum Branchings" by R.E. Tarjan [8], an e f f i c i e n t implementation of t h e algorithm [2,5,61 f o r computing an optimum branching i n a d i r e c t e d graph G = (V,E) i s described. Algorithm BRANCH of [81 c o n s t r u c t s a subgraph G ( H ) = (V,H) of G. When t h e algorithm i s completed, it i s claimed t h a t an optimum branching of G can be e x t r a c t e d from H v i a a depth f i r s t search. This claim i s based upon lemma 2 , which states t h a t t h e r e i s always a unique simple p a t h i n G ( H ) leading from any vertex v of any root component S o f G ( H ) t o any vertex w of t h e weakly connected component W containing S. However, lemma 2 i s i n c o r r e c t , as shown by t h e following counterexample. Let u s apply algorithm BRANCH t o t h e graph G i n f i g . 1( a ) , where numbers on edges a r e values. Fig. l ( b ) , ( c ) and (d) represent a possible sequence of graphs G ( H ) obtained a f t e r each execution of s t e p G8. I f we take S = {1,2,3,4) = W , v = l and w=3 i n G ( H ) of f i g . l ( d ) , t h e r e a r e tWo simple paths (of d i f f e r e n t values) from v t o w. Hence, a f t e r d e l e t i n g edge ( 4 , l ) from G ( H ) , a depth f i r s t search on t h e r e s u l t i n g graph cannot guarantee t o e x t r a c t from it an optimum branching of G. NevertheNetworks, Vol. 9 (1979) 309-312 01979 John Wiley & Sons, Inc.

0028-3045/79/0009-0309$01.00

310

CAMERINI, FRATTA AND MAFFIOLI

less, s i n c e t h e r e s u l t s of [6,7] imply t h a t t h e f i n a l set H does c o n t a i n an optimum branching o f G , t h e method f o r f i n d i n g GCH) i s v a l i d , b u t t h e i n c o r r e c t n e s s of lemma 2 r e q u i r e s t h a t w e update and memorize, a f t e r each update of H, the n e s t e d s h r i n k i n g s t r u c t u r e of G ( H ) . This a l l o w s us t o perform a backward expansion of t h e root components, t h u s c o r r e c t l y recoveri n g an optimum branching. Many bookkeeping mechanisms could be u t i l i z e d t o this purpose. One of them, having the d e s i r a b l e p r o p e r t y o f n o t a f f e c t i n g the complexity e v a l u a t i o n s of [81, i s h e r e o u t l i n e d and d i s c u s s e d i n d e t a i l i n [31. G(H) 10

3

$12 04

3

b

3

Ptg. 1 A t t h e beginning o f BRANCH, a

forest F i s i n i t i a l i z e d t o b e an empty f o r e s t , w i t h no nodes and no arcs. Each t i m e an edge !u,v) i s added t o H i n BRANCH, a new node i s a l s o added t o F, SO t h a t t h e nodes o f F are maintained t o r e p r e s e n t t h e edges i n H. The a r c s o f F are c o n s t r u c t e d as f o l l o w s . Whenever (u,v) i s chosen t o e n t e r a root component S c o n t a i n i n g more t h a n one v e r t e x , l e t ( x l , y l ) , (x2,y2) , ( s , y k ) be t h e

...,

sequence of edges determined i n BRANCH, s t e p G5, such t h a t edge -i< k , an ( \ , y k ) w a s added t o H t o form S . Then, f o r each i , l < a r c i s added t o

F,

d i r e c t e d from node ( u , v ) t o node ( x i , y i ) ,

so

F and ( u , v ) i s the parent

t h a t (xi,yi)

i s a chiZd of ( u , v ) i n

of ( x i , y i ) .

I n case S c o n t a i n s a unique v e r t e x , a p o i n t e r A(v) =

( u , v ) i s set from v t o t h e leaf ( u , v ) . During t h e c o n s t r u c t i o n o f F w e also need t o keep t r a c k o f t h e s e t N of a l l PO06 nodes o f F, i . e . t h e nodes which have no p a r e n t . Fig. 2 i l l u s t r a t e s t h e f i n a l f o r e s t F o b t a i n e d i n t h e example of f i g . 1. Note t h a t , s i n c e H does n o t c o n t a i n more than 2n-2 edges ( n = l v l ) [8] , t h e t o t a l number o f nodes and a r c s of F i s O ( n ) . Therefore the computation of F does n o t i n c r e a s e t h e complexity of BRANCH.

NOTE ON OPTIMUM BRANCHINGS

311

Fig. 2 Once t h e algorithm i s completed, an optimum branching of G can be obtained from F i n t h e following way. L e t R be t h e s e t of r o o t v e r t i c e s which algorithm ROOT would select i f applied t o a l l root components of G ( H ) . ( R = {min(i) I i ~ r s e t ~ see : s e c t i o n 3 of [81.) I n i t i a l i z e a void s e t B, i n i t i a l i z e N t o t h e s e t of r o o t nodes of F and repeat steps L1-L3 below until R = N = ~ .

Algorithm LEAF: L1:

I f R # pI, d e l e t e a r o o t v e r t e x v from R , else p i c k any r o o t node (w,v) € N and add it t o B.

L2:

I d e n t i f y t h e (possibly t r i v i a l ) path P i n f leading from a r o o t node t o t h e l e a f (u,v) = XCv)

L3:

Delete from F a l l nodes of P and a l l a r c s d i r e c t e d o u t of these nodes ( t h i s s t e p updates t h e set N of t h e r o o t nodes)

.

The i d e n t i f i c a t i o n of s t e p L2 can be e a s i l y made by t r a c i n g P i n the child-to-parent d i r e c t i o n , u n t i l a r o o t node i s found. As it can be seen i n the example of f i g . 1 and 2 , t h e f i n a l set B obtained by algorithm LEAF i s { ( 1 , 2 ) , ( 2 , 3 ) , ( 2 , 4 ) which i d e n t i f i e s an optimum branching of G and shows, f o r t h i s example, t h e correctness of the above algorithm. I t s formal proof i s obtained by induction and can be found i n [3] f o r t h e case of spanning arborescences. Since algorithm LEAF c o n s i s t s e s s e n t i a l l y of v i s i t i n g each node of F exactly once, i t s complexity i s O h ) . Hence a l l the complexity r e s u l t s given i n [81 a r e s t i l l valid. For what concerns t h e version of algorithm BRANCH described i n s e c t i o n 3, it has t o be pointed o u t t h a t c ( x , y ) and c ( i , j f should r e f e r t o values updated as i n s t e p G7, r a t h e r than t h e o r i g i n a l values of t h e given digraph. This f u r t h e r d i f f i c u l t y can be overcome by noting [9] t h a t t h e only values which a r e

312

CAMEFUNI, FRATTA AND MAFFIOLI

used by t h e a l g o r i t h m are t h o s e of edges either about t o be added t o H , o r a l r e a d y i n H b u t n o t i n a s t r o n g component. An edge i s added t o H o n l y when it i s r e t u r n e d by a c a l l on MAX. By using an i d e a of 1 1 3 , MAX can be e a s i l y modified t o r e t u r n the updated v a l u e o f t h e edge, as w e l l as t h e edge i t s e l f . (See E41 f o r a d i s c u s s i o n of how t o implement MAX, ADD and Once an edge i s added t o H I f u r t h e r updates do n o t QUNION.) a f f e c t i t s v a l u e . ( S t e p G7 o n l y u p d a t e s unexamined edges.) REFERENCES

1.

Aho, A.V., J . E . Hopcroft and J . D . ullman, "On F i n d i n g Opt i m u m Ancestors i n Trees", SIAM J . Comput, , 5 , 1976, pp. 115-132.

2.

Bock, F . , "An Algorithm t o C o n s t r u c t a Minimum D i r e c t e d Spanning Tree i n a D i r e c t e d Network", Developments i n Operations Research, Gordon and Breach, New York, 1971, pp. 29-44.

3.

Camerini, P.M., L. F r a t t a and F. M a f f i o l i , "The K B e s t Spanning Arborescences of a Network" , t o b e p u b l i s h e d .

4.

C h e r i t o n , D. and R. T a r j a n , "Finding M i n i m u m Spanning T r e e s " , SIAM J . Comput. 5 , 1976, PP. 724-742.

5.

Chu, Y . J . and T.H. L i n , "On t h e S h o r t e s t Arborescence o f a D i r e c t e d Graph" , S e i . Siniea, 1 4 , 1965 , pp. 1396-1400.

6.

Edmonds, J.

7.

K a r p , R.M., "A Simple D e r i v a t i o n o f Edmonds' Algorithm f o r Optimum Branchings", Networks, 1, 1971, pp. 265-272.

8.

T a r j a n , R . E . , "Finding Optimum Branchings" , Ne&orks, 1977, pp. 25-35.

9.

T a r j a n , R.E.,

, "Optimum Branchings", Jow,. of Research of The NationaZ Bureau o f Standards, 71B, 1967, pp. 233-240.

p r i v a t e communication.

7,