On Bounded Diameter MST Problem on Random Instances Edward Kh. Gimadi1,2 , Alexey M. Istomin1 , and Ekaterina Yu. Shin2 1 Sobolev Institute of Mathematics, 4 Acad. Koptyug avenue, 630090, Novosibirsk, Russia 2 Novosibirsk State University, 2 Pirogova Str. 630090, Novosibirsk, Russia gimadi@math.nsc.ru, alexeyistomin@gmail.com, katherine15963@gmail.com Abstract. We give an approximation deterministic algorithm for solv- ing 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 dis- tributed random variables on an interval (an ; bn ). Conditions of asymp- totic optimality are presented. Keywords: Graph · Bounded diameter minimum spanning tree · Min- imum spanning tree · Asymptotically optimal algorithm · Probabilistic analysis · Performance guarantees · Random inputs · Uniform 1 Introduction 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 find 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 = |E| and n = |V |. In current paper a modification of the classical MST is studied. We study a bounded diameter minimum spanning tree problem (BDMST). The goal is to find 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 fields 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 160 E. Kh. Gimadi et al. 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 communi- cation 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 classified into tree cate- gories: exact methods, heuristic methods with experimentally measured perfor- mance 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 ra- tio, there was presented [1] a greedy heuristic algorithm - the One Time Tree Construction (OTTC) for solving the BDMST problem followed by its mod- ification [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 first 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 diame- ter 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 func- tion 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 n o  Pr FA (I) > 1 + εA (n) OP T (I) ≤ δ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, On BDMST Problem 161 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 → ∞. Apparently, judging by the review article [33], the first 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 uni- form 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 diam- eter 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 first stage algorithm A e 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 ∈ 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 A e has the following performance guarantees:  b /a  n n −0.25(n−d) n = O n−1 , δn = e . n/ ln n−d Thus, the sufficient conditions for the asymptotic optimality of the algorithm A e are n bn /an ≤ , d = o(n). ln 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 \ V1 . 162 E. Kh. Gimadi et al. Stage 2. Every vertex u ∈ V2 is connected by the shortest possible edge with a vertex v ∈ 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 \ v 0 , where v 0 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 distribu- tion on a set (an , bn ), 0 < an ≤ bn < ∞. Further we suppose that the parameter d is defined 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 = u∈V2 φdu , φdu is a random P 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 X W (T0 ) = φdei . i=1 φd u −an Or using variables ξud , where ξud = bn −an , distributed on [0, 1], we get d−1 X W (T0 ) = (d − 1)an + (bn − an ) ξedi = (d − 1)an + (bn − an )W (T0 )0 . i=1 Pd−1 We denote W (T0 )0 = i=1 ξedi . Denote S 0 = u∈V2 ξud . Obviously, P S = (n − d)an + S 0 (bn − an ). On BDMST Problem 163 ξud is a random variable equal to minimum from d identically independent dis- tributed random variables with uniform distribution on an interval [0, 1]. We have W (TA ) = (n − 1)an + (bn − an )(W (T0 )0 + S 0 ). Statement 3. We can estimate the expectation of W (T0 )0 by the sum 1 1 1 + + . . . + ≤ ln d 2 3 d 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 bn (h ln d + (1 + λn )ES 0 ) εn = . (2) an n−1 Statement 4.  Pr WA ≤ (1 + εn )OP T ≥ 1 − δn , (3) where δn = Pr S 0 > (1 + λn )ES 0 .  (4) Proof. WA (n − 1)an + (bn − an )(W (T0 )0 + S 0 ) bn (h ln d + S 0 ) ≤ =≤ 1 + . OP T (n − 1)an an n−1 By virtue of formulas (2) and (3) the inequality can be continued with the probability 1 − δn . WA bn (h ln d + S 0 ) bn (h ln d + (1 + λn )ES 0 ) ≤1+ ≤1+ = 1 + εn . OP T an n−1 an n−1 The Statement 4 is proved. Statement 5. n−d ES 0 = . d Proof. S 0 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   bn (h ln d + (1 + λn )(n − d)/d) bn h ln d 1 + λn εn = ≤ + . (5) an n−1 an n − 1 d 164 E. Kh. Gimadi et al. 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 n g t2 o k EetXk ≤ exp . (6) 2 Pn Pn Put S = k=1 Xk and G = k=1 gk . Then   x2 exp −2G , for 0 ≤ x ≤ GT, Pr{S > x} ≤ exp − T2x , if x ≥ GT. Theorem 1. Let the parameter d be defined so that ln n ≤ d < n. (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. q Put λn = 4 ln n n . According to the formula (5)   bn h ln d 1 + λn εn ≤ + . an n−1 d We see that εn → 0 under condition bn = o(dn ). an Now using Petrov’s Theorem estimate the fault probability δn = Pr S 0 > (1 + λn )ES 0 ,  Put d T = ; 2 n−d G= ; d2 n−d x = λn ES 0 = λn . d On BDMST Problem 165 The inequality T G > x is satisfied. Indeed from 1n−d n−d TG = > x = λn ES 0 = λn 2 d d it follows that r 1 4 ln n > λn = . 2 n According to Petrov’s Theorem, we have an estimate for the failure proba- bility of the algorithm A: n x2 o δn = Pr{Ŝ 0 > x} ≤ exp − . 2G Now show that x2 ≥ ln n. 2G Indeed, since n − d ≥ n2 , according to inequality (7), we get  2 x 2 λn (n−d) d (n − d) 2 n − d  4 ln n  = = λn = ≥ ln n. 2G 2 (n−d) d2 2 2 n From this it follows that n x2 o 1 δn = Pr{S 0 > x} ≤ exp − ≤ exp(− ln n) = → 0, 2G n as n → ∞. So in the Case 1 Algorithm A solves the problem asymptotically optimal. Case 2 : n/2 ≤ d < n − 1. Put λn = ln n. According to the formula (5)   bn h ln d 1 + λn εn ≤ + . an n−1 d We see that within the values of the parameter d fot the case  2, the  expression bn ln n in parentheses reaches a maximum at d = n/2 .So εn = O an n and εn → 0 under condition bn  n  =o . an ln n Now using Petrov’s Theorem estimate the fault probability δn = Pr S 0 > (1 + λn )ES 0 ,  166 E. Kh. Gimadi et al. Put d T = ; 2 (n − d) G= ; d2 n−d x = λn ES 0 = ln n . d The inequality T G < x is satisfied. 1 (n − d) (n − d) TG = < x = ln n . 2 d d According to Petrov’s Theorem, we have an estimate for the failure proba- bility of the algorithm A: n Txo δn = Pr{S 0 > x} ≤ exp − . 2 Now Tx d (n − d) = ln n ≥ ln n. 2 2 d From this it follows that n Txo 1 δn = Pr{Ŝ 0 > x} ≤ exp − ≤ exp(− ln n) = → 0, 2 n as n → ∞. 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 infinite support like exponential or truncated-normal distribution, (b) the problem of finding several edge-disjointed spanning trees with a bounded diameter. Acknowledgement. Authors are supported by the Russian Foundation for Ba- sic Research (project 16-07-00168), and by the program of fundamental scientific researches of the SB RAS I.5.1. References 1. Abdalla, A., Deo, N., Gupta P.: Random-tree diameter and the diameter con- strained MST. In: Proceedings of Congress on Numerantium. pp. 161–182 (2000) On BDMST Problem 167 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 bounded- depth 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 Fran- cisco (1979) 11. Gimadi, E. Kh., Perepelitsa, V. A.: On a problem of finding 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 trav- eling 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 Rus- sian) 14. Gimadi, E. Kh., Serdyukov, A. I.: A probabilistic analysis of approximation algo- rithm 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 mini- mum 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 span- ning 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 min- imum 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: 168 E. Kh. Gimadi et al. Proceedings of Genetic and Evolutionary Computational Conference (GECCO- 2006). 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 permu- tations and random keys. In: Proceedings of Genetic and Evolutionary Computa- tional 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 effective 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 finding 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 algo- rithm 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)