On Bounded Diameter MST Problem on Random Instances

Abstract

We give an approximation deterministic algorithm for solving the Random bounded diameter minimum spanning tree (BDMST) problem on an undirected graph. The algorithm has a quadratic time complexity. A probabilistic analysis was performed under conditions that edge weights of given graph are identically independent uniformly distributed random variables on an interval (an; bn). Conditions of asymptotic optimality are presented.

Keywords

• Graph
• Bounded diameter minimum spanning tree
• Min- imum spanning tree
• Asymptotically optimal algorithm
• Probabilistic analysis
• Performance guarantees
• Random inputs
• Uniform

-

The Minimum Spanning Tree (MST) problem is a one of the classic discrete optimization problems. Given undirected weighted graph G = (V; E), MST is to nd a spanning tree of a minimal weight. MST is polynomially solvable, there are classic algorithms by Boruvka (1926), Kruskal (1956) and Prim (1957). These algorithms have complexity O(n2) and O(M log n) where M = jEj and n = jV j.

In current paper a modi cation of the classical MST is studied. We study a bounded diameter minimum spanning tree problem (BDMST). The goal is to nd in the graph Gn a spanning tree Tn of minimal total weight having its diameter limited by given number d. The diameter of a tree is the number of edges on the longest path between two leaves in the tree. This problem is N P hard in the common case [ 10 ].

The Bounded Diameter Minimum Spanning Tree Problem has many practical applications in various elds such as telecommunication networks and linear Copyright c by the paper's authors. Copying permitted for private and academic purposes.

In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org light wave network design [ 5 ], bit compression for information retrieval [ 7 ] and distributed mutual exclusion [ 28, 30, 31, 34 ].

A good example of usage is the Distributed Mutual Exclusion algorithms. Here we have a computer network of k computers and the internal communication is done by sending messages between computers along a tree. Only One Computer is Allowed to Enter a Critical Section. If Some Computer Wants the Right to Enter a Critical Section It must request it by sending a message to the computer which currently has this right. The time of this request depends on the number of edges in the path to the computer with the right. The goal is to build a communication tree with the minimal cost and bounded time of communication. And the solution is exactly the Bounded Diameter Minimum

Spanning Tree.

Techniques for solving the BDMST problem may be classi ed into tree categories: exact methods, heuristic methods with experimentally measured performance ratio and algorithms with guaranteed performance ratio.

There are exact approaches for solving the BDMST problem based on mixed linear integer programming [ 2 ], [ 17 ] and 0-1 integer linear programming based branch and cut approaches [ 18 ]. But, these approaches could only be used to solve small problem instances, like complete graphs with less than 100 nodes.

As for the heuristic methods with experimentally measured performance ratio, there was presented [ 1 ] a greedy heuristic algorithm - the One Time Tree Construction (OTTC) for solving the BDMST problem followed by its modi cation [ 27 ], called Randomized Greedy Heuristics (RGH). Later it was also studied and extended in [ 32 ] and [ 6 ]. Genetic algorithms for solving BDMST problems were considered as well [ 26 ], [ 21 ], [ 22 ], [ 23 ]. Local search approaches were considered in [ 19 ], [ 20 ].

There were not really much attempts to solve BDMST by algorithms with guaranteed performance ratio. A study was done in [ 3 ], however the proof in not really easy to follow. In this paper we give the rst approximation deterministic polynomial time algorithm for solving the Random DBMST on an undirected graph.

In the papers [ 15, 14 ] this problem was studied with a graph diameter bounded from below. In the current paper we consider the problem with a graph diameter bounded from above. We introduce a polynomial-time algorithm to solve this problem and provide conditions for this algorithm to be asymptotically optimal. A probabilistic analysis was performed under conditions that edges weights of given graph are identically independent distributed random variables.

By FA(I) and OP T (I) we denote respectively the approximate (obtained by some approximation algorithm A) and the optimum value of the objective function of the problem on the input I. An algorithm A is said to have performance guarantees "A(n); A(n) on the set of random inputs of the problem of the size n, if

PrnFA(I) > 1 + "A(n) OP T (I)o

A(n); (1) where "A(n) is an estimation of the relative error of the solution obtained by algorithm A, A(n) is an estimation of the failure probability of the algorithm, which is equal to the proportion of cases when the algorithm does not hold the relative error "A(n) or does not produce any answer at all.

Following by [ 13 ], we say that an algorithm A is called asymptotically optimal on the class of instances of the problem, if there are exist such performance guarantees that "A(n) ! 0 and A(n) ! 0 as n ! 1. Apparently, judging by the review article [ 33 ], the rst examples of asymptotically optimal algorithms were presented in the works [ 11, 12 ] for the traveling salesman problem on random input data.

Let's denote UNI(an; bn) a class of complete graphs with n vertices where edge weights are independent identically distributed random variables with uniform distribution on an interval (an; bn).

Frieze shown that the mathematical expectation of weight of classic MST on a random graph can be unexpectedly small. So for example on a complete graph with weights of edges from class U N I(0; 1), the weight of a MST w.h.p. (with high probability) is close to the constant 2.02 ... [ 9 ].

As it was said in the papers [ 14, 15 ] the MST was studied with a graph diameter bounded from below. In [ 14 ] presented an asymptotically optimal algorithm Ae with time-complexity O(n2) for graphs which belong to UNI(an; bn)-class. On the rst stage algorithm Ae build a d-vertex path P , using the greedy strategy "Go to the nearest unexplored vertex" , starting from an arbitrary vertex. On the second stage in a graph G with edge weights equal to an for all e 2 P , by means of Prim's algorithm [ 25 ], a spanning tree of a minimal weight is built.

This tree is taken as a solution.

On graphs which belong to UNI(an; bn) class algorithm Ae has the following performance guarantees: n = O

bn=an n= ln nn d1 ; n = e 0:25(n d): Thus, the su cient conditions for the asymptotic optimality of the algorithm Ae are

n bn=an ln n ; d = o(n):

Next, let's proceed to the description of the algorithm for solving the BDMST problem. 2

An Algorithm A for Finding a Bounded Diameter MST

Let d be a parameter exceeding the tree diameter.

Stage 1. Arbitrary select d vertices subset from V , let's denote selected subset V1. Using the Prim's algorithm [ 25 ] construct in the graph G[d] induced by these d vertices a minimum spanning tree T0: edge by edge grow up tree by edges e1; : : : ; ed 1. Obviously, its diameter is smaller than the parameter d. Put V2 = V n V1.

Stage 2. Every vertex u 2 V2 is connected by the shortest possible edge with a vertex v 2 V1. As a result we obtain an n-vertex tree TA which is an approximate solution of the problem.

A comment. If the constructed tree T0 has the form of a chain, then the nearest vertices v are selected from the set V1 n v0, where v0 is one of the two end vertices of the chain.

Finally we built the spanning tree TA with a diameter smaller than the parameter d.

Further, we denote by W (G0) the weight of the subgraph G0 of the given graph G, by WA the weight of the solution built by algorithm A. Also by EX we will denote an expectation of a random variable X and by VarX its variance. 3

Analysis of Algorithm A

The algorithm has polynomial complexity O(n2), since the construction of the tree T0 in Stage 1 is done by the Prim's algorithm [ 25 ] in time O((n d)2), and in the Stage 2 it takes about d(n d) comparison operations.

A probabilistic analysis we perform under conditions that graph edges weights are identically independent distributed random variables with uniform distribution on a set (an; bn), 0 < an bn < 1. Further we suppose that the parameter d is de ned on the set of values d in the range ln n d < n.

Statement 1. The spanning tree TA is restricted by a diameter not exceeding d, since on the second Stage the diameter of the tree T0 can increase by no more than 1.

Statement 2. W (TA) = W (T0) + S, where S = Pu2V2 du, du is a random variable equal to minimum from d identically independent distributed random variables from with uniform distribution on an interval [an; bn], an > 0.

Also, according to step 1 of the algorithm A, weight of selected edge ei is a random variable equal to minimum from i identically independent distributed random variables from with uniform distribution on an interval [an; bn], an > 0.

So,

d 1 W (T0) = X

edi : i=1 d 1 an) X

i=1 Or using variables ud, where ud = bndu aann , distributed on [0; 1], we get W (T0) = (d ud is a random variable equal to minimum from d identically independent distributed random variables with uniform distribution on an interval [0; 1].

We have

W (TA) = (n for the expectation of the length ECh ln d, were Ch is a chain in G[d], obtained by the greedy procedure "Go to the nearest city". So we have W (T0)0 h ln d w.h.p., where the constant h is large 1.

Let n be a positive constant. Denote

Statement 4.

where Proof.

"n = bn (h ln d + (1 + n)ES0) an n 1

: Pr WA (1 + "n)OP T 1

n; n = Pr S0 > (1 + n)ES0 : (2) (3) (4) WA OP T (n 1)an + (bn (n an)(W (T0)0 + S0) 1)an = 1 + bn (h ln d + S0) an n 1 :

By virtue of formulas (2) and (3) the inequality can be continued with the probability 1 n.

WA OP T 1 + bn (h ln d + S0) an n 1 1 + bn (h ln d + (1 + n)ES0) an n 1 = 1 + "n:

The Statement 4 is proved.

Statement 5.

ES0 = n d d : Proof. S0 is equal to the sum of n d random independent identically distributed variables each of them equal to minimum over d 1 uniformly distributed on a segment [0; 1] variables.

Using the statement 5 we have the following expression for the "n "n = bn (h ln d + (1 + n)(n an n 1 d)=d) bn an +

Next for the probabilistic analysis of Algorithm A we need the following

Petrov's Theorem [ 24 ]. Consider independent random variables X1; : : : ; Xn. Let there be positive constants g1; : : : ; gn and T such that for all 1 k n and 0 t T

EetXk expn gkt2 o: 2 Put S = Pn k=1 gk. Then k=1 Xk and G = Pn

PrfS > xg exp exp 2G2 T2x; f;orif 0x x x

GT; GT: Theorem 1. Let the parameter d be de ned so that ln n d < n: (6) (7) Then Algorithm A solves the problem asymptotically optimal w.h.p. Proof. We introduce a proof for two cases for a values of the parameter d: ln n d < n=2 and n=2 d < n 1.

Case 1: ln n

d < n=2: Put n = q 4 lnn n .

According to the formula (5)

We see that "n ! 0 under condition

Now using Petrov's Theorem estimate the fault probability Put

"n bn an bn = o(dn): an n = Pr S0 > (1 + n)ES0 ; d T = ;

2 G = n d

d2 ; x = nES0 = n n d d :

The inequality T G > x is satis ed. Indeed from

2xG2 =

(n d) 2 n d 2 (nd2d) exp n exp( ln n) = n1 ! 0; as n ! 1. So in the Case 1 Algorithm A solves the problem asymptotically optimal.

Put n = ln n.

According to the formula (5)

Case 2 : n=2 d < n

1: "n bn an nh ln d1 + 1 +d n : We see that within the values of the parameter d fot the case 2, the expression in parentheses reaches a maximum at d = n=2 .So "n = O bnanlnnn and "n ! 0 under condition

abnn = o lnnn :

Now using Petrov's Theorem estimate the fault probability

n = Pr S0 > (1 + n)ES0 ;

The inequality T G < x is satis ed.

According to Petrov's Theorem, we have an estimate for the failure probability of the algorithm A: ; n d d

Put

G =

T = as n ! 1. So in the Case 2 Algorithm A solves the problem asymptotically optimal as well.

Theorem 1 is completely proved.

4

Conclusion It would be interesting to investigate (a) the Random BDMST problem on input data with in nite support like exponential or truncated-normal distribution, (b) the problem of nding several edge-disjointed spanning trees with a bounded diameter.

Acknowledgement. Authors are supported by the Russian Foundation for Basic Research (project 16-07-00168), and by the program of fundamental scienti c researches of the SB RAS I.5.1.

References

1. Abdalla , A. , Deo , N. , Gupta P. : Random-tree diameter and the diameter constrained MST . In: Proceedings of Congress on Numerantium . pp. 161 { 182 ( 2000 )

2. Achuthan , N.R. , Caccetta , L. , Caccetta , P. , Geelen , A. : Computational Methods for the Diameter Restricted Minimum Weight Spanning Tree Problem . Australian Journal of Combinatorics 10 , 51 { 71 ( 1994 )

3. Angel , O. , Flaxman , A. D. , Wilson, D. B.: A sharp threshold for minimum boundeddepth and bounded-diameter spanning trees and Steiner trees in random networks . Preprint; arXiv:0810.4908v2 [math.PR] ( 2011 )

4. Angluin , D. , Valiant , L. G. : Fast probabilistic algorithms for Hamiltonian circuits and matchings . Journal of Computer and System Sciences 18 ( 2 ), 155 { 193 ( 1979 )

5. Bala, K. , Petropoulos , K. , Stern , T. E.: Multicasting in a linear lightwave network . In: Proceedings of IEEE INFOCOM'93 . pp. 1350 { 1358 ( 1993 )

6. Binh , H. T. T., Hoai , N. X. , McKay , R. I. I.: A new hybrid genetic algorithm for solving the bounded diameter minimum spanning tree problem . In: Proceedings of IEEE World Congress on Computational Intelligence , Hong Kong, LNCS ( 2008 )

7. Bookstein , A. , Klein , S. T.: Compression of correlated bit . Inf. Syst . 16 , 110 { 118 ( 1996 )

8. Cooper , C. , Frieze , A. , Ince , N. , Janson , S. , Spencer , J.: On the length of a random minimum spanning tree . Combinatorics, Probability and Computing 25 ( 1 ), 89 { 107 ( 2016 )

9. Frieze , A. : On the value of a random MST problem . Discrete Applied Mathematics 10 , 47 { 56 ( 1985 )

10. Garey , M. R. , Johnson, D. S.: Computers and Intractability. Freeman, San Francisco ( 1979 )

11. Gimadi , E. Kh. , Perepelitsa , V. A. : On a problem of nding minimal Hamiltonian circuit with weighted arcs . Disckretni analiz, Novosibirsk , 15 , 57{ 65 ( 1969 ), (in Russian)

12. Gimadi , E. Kh. , Perepelitsa , V. A. : An asymptotical approach to solving the traveling salesman problem . Upravljaemye sistemy, Novosibirsk , 12 , 35{ 45 ( 1974 ), (in Russian)

13. Gimadi , E. Kh. , Glebov , N. I. , Perepelitsa , V. A. : Algorithms with Estimates for Discrete Optimization Problems . Problemy Kibernetiki 31 , 35 { 42 ( 1975 ), (in Russian)

14. Gimadi , E. Kh. , Serdyukov , A. I.: A probabilistic analysis of approximation algorithm for tree spanning problem with a bounded from below diameter In: Oper. Res. Proceed . 99 ( Inderfurth K. ed.). pp. 63 { 68 . Springer, Berlin ( 2000 )

15. Gimadi , E. Kh. , Shin , E. Yu. : Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded below . Journal of Applied and Industrial Mathematics 9 ( 4 ), 480 { 488 ( 2015 )

16. Gimadi , E. Kh. , Istomin , A. M. , Shin , E. Yu. : On algorithm for the minimum spanning tree problem bounded below . In: Proc. DOOR 2016 , Vladivostok, Russia, September 19-23 , 2016 . CEUR-WS . vol. 1623 , pp. 11 { 17 ( 2016 )

17. Gouveia , L. , Magnanti , T.L. , Requejo C. : A 2-path approach for odd diameter constrained minimum spanning and steiner trees . Network 44 ( 4 ), 254 { 265 ( 2004 )

18. Gruber , M. , Raidl G.R.: A New 0-1 ILP approach for the bounded diameter minimum spanning tree problem . In: Proceedings of the 2nd International Network Optimization Conference . pp. 178 - 185 ( 2005 )

19. Gruber , M. , Raidl , G.R. : Variable neighbourhood search for the bounded diameter minimum spanning tree problem . In: Proceedings of the 18th Mini Euro Conference on Variable Neighborhood Search , Spain ( 2005 )

20. Gruber , M. , Hemert , J. , and Raidl , G.R. : Neighbourhood searches for the bounded diameter minimum spanning tree problem embedded in a VNS, EA and ACO . In: Proceedings of Genetic and Evolutionary Computational Conference (GECCO2006) . pp. 1187 { 1194 ( 2006 )

21. Julstrom , B.A. , Raidl , G.R.: A permutation coded evolutionary for the bounded diameter minimum spanning tree problem . In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2003) . pp. 2 - 7 ( 2003 )

22. Julstrom , B.A. : Encoding bounded diameter minimum spanning trees with permutations and random keys . In: Proceedings of Genetic and Evolutionary Computational Conference (GECCO-2004). LNCS . vol. 3102 , pp. 1272 - 1281 ( 2004 )

23. Nghia , N. D. , Binh , H. T. T.: A new recombination operator for solving bouded diameter minimum spanning tree problem . In: Proceedings of RIVF-2007 , LNCS ( 2007 )

24. Petrov , V. V. : Limit Theorems of Probability Theory. Sequences of Independent Random Variables . Clarendon Press, Oxford, 304 p. ( 1995 )

25. Prim , R. C.: Shortest connection networks and some generalizations . Bell System Tech. J . 36 , 1389 { 1401 ( 1957 )

26. Raidl , G.R. , Julstrom , B.A. : Edge-sets: an e ective evolutionary coding of spanning trees . IEEE Transactions on Evolutionary Computation 7 , 225 { 239 ( 2003 )

27. Raidl , G.R. , Julstrom , B.A. : Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem . In: Proceeding of the ACM Symposium on Applied Computing . pp. 747 { 752 ( 2003 )

28. Raymond , K. : A tree-based algorithm for distributed mutual exclusion . ACM Trans Comput Syst 7 , 61 { 77 ( 1989 )

29. Roskind , J. , Tarjan , R. E.: Note on nding minimum-cost edge-disjoint spanning trees . Math. Oper. Res . 10 ( 4 ), 701 { 708 ( 1985 )

30. Satyanarayanan , R. , Muthukrishnan , D. R.: A note on Raymond's tree-based algorithm for distributed mutual exclusion . Inf Process Letters 43 , 249 { 255 ( 1992 )

31. Satyanarayanan , R. , Muthukrishnan , D. R.: A static tree-based algorithm for the distributed readers and writers problem . Comput Sci Inform 24 , 21 { 32 ( 1994 )

32. Singh , A. , Gupta , A.K. : An impoved heuristic for the bounded diameter minimum spanning tree problem . Journal of Soft Computing 11 , 911 { 921 ( 2007 )

33. Slominski , L. : Probabilistic analysis of combinatorial algorithms: a bibliography with selected annotations . Computing 28 , 257 { 267 ( 1982 )

34. Wang , S. , Lang , S. D. : A Tree-based Distributed Algorithm for the K-entry Critical Section Problem . In: Proceedings of the 1994 International Conference on Parallel and Distributed Systems . pp. 592 { 597 ( 1994 )