=Paper=
{{Paper
|id=Vol-2098/paper14
|storemode=property
|title=On Bounded Diameter MST Problem on
Random Instances
|pdfUrl=https://ceur-ws.org/Vol-2098/paper14.pdf
|volume=Vol-2098
|authors=Edward Kh. Gimadi,Alexey M. Istomin,Ekaterina Yu. Shin
}}
==On Bounded Diameter MST Problem on
Random Instances==
https://ceur-ws.org/Vol-2098/paper14.pdf
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)