=Paper=
{{Paper
|id=Vol-1623/paperco4
|storemode=property
|title=On Algorithm for the Minimum Spanning Trees Problem with Diameter Bounded Below
|pdfUrl=https://ceur-ws.org/Vol-1623/paperco4.pdf
|volume=Vol-1623
|authors=Edward Kh. Gimadi, Alexey Istomin, Ekaterina Shin
|dblpUrl=https://dblp.org/rec/conf/door/GimadiIS16
}}
==On Algorithm for the Minimum Spanning Trees Problem with Diameter Bounded Below==
https://ceur-ws.org/Vol-1623/paperco4.pdf
On Algorithm for the Minimum Spanning Trees
Problem with Diameter Bounded Below
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, Shinus90@yandex.ru
Abstract. The minimum spanning trees problem is to find k edge-disjoint
spanning trees in a given undirected weighted graph. It can be solved in poly-
nomial time. In the k minimum spanning trees problem with diameter bounded
below (k-MSTBB) there is an additional requirement: a diameter of every span-
ning tree must be not less than some predefined value d. The k-MSTBB is N P -
hard. We propose an asymptotically optimal polynomial time algorithm to solve
this problem.
Keywords: minimum spanning tree, minimum spanning trees problem, asymp-
totically optimal algorithm, probabilistic analysis, bounded below, performance
guarantees, random inputs
Introduction
The Minimum Spanning Tree (MST) problem is one of the classic discrete optimization
problems. Given G = (V, E) undirected weighted graph, the MST is to find a spanning
tree of a minimal weight. The 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 |.
The Minimum Spanning Tree with diameter Bounded Below (MSTBB) problem is
a natural generalization of the MST problem. In the MSTBB aim is to find a spanning
tree of a minimal weight such that its diameter is not less than some predefined value
d. Diameter of a tree is defined as the number of edges on the longest path between two
leaves in the tree. The MSTBB is studied in [6]. It is NP-hard since with dn = n − 1
it is equivalent to the problem of finding Hamiltonian Path of a minimal weight in a
given graph. Moreover if dn is constant then the MSTBB can be solved in polynomial
time by iterating through all possible simple paths consisting exactly of dn edges. Thus
MSTBB is actual with dn growing.
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
Copyright ⃝
c by the paper’s authors. Copying permitted for private and academic purposes.
In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org
12 Edward Kh. Gimadi, Alexey M. Istomin, Ekaterina Yu. Shin
problem on(the input I. )According to [5] 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
{ ( ) }
Pr FA (I) > 1 + εA (n) OP T (I) ≤ δA (n), (1)
where εA (n) is an assessment 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.
An algorithm A is called asymptotically optimal on the class of instances of the
problem, if there are such performance guarantees that εA (n) → 0 and δA (n) → 0 as
n → ∞.
Let us denote by UNI(an , bn ) a class of complete graphs with n vertices where
weights of edges are independent identically distributed random variables with uniform
distribution on a segment [an , bn ]. By EXP(an , αn ) we will denote a class of complete
graphs with n vertices where weights of edges are independent identically distributed
random variables with exponential distribution with a probability function
{ ( )
1
exp − x−an
, if an ≤ x < ∞,
p(x) = αn αn
0, otherwise.
And by N(an , σn ) we will denote a class of complete graphs with n vertices where
weights of edges are independent identically distributed random variables with cutted-
normal distribution with a probability function
{ ( 2
)
√ 2 2 exp − (x−a2σn
n)
2 , if an ≤ x < ∞,
p(x) = 2πσn
0, otherwise.
In [6] presented an asymptotically optimal algorithm A e with complexity O(n2 ) for
graphs which belong to UNI(an , bn ) class. On the first stage algorithm A e build a path
P = {(i0 , i1 ), (i1 , i2 ), . . . , (id−1 , id )} of d edges starting from an arbitrary vertex i0
and enlarging it by adding successive edges of a minimal weight. On the second stage
a spanning tree of a minimal weight D fn which contains path P is built using Prim
algorithm. Built tree is taken as a solution.
The algorithm A e on graphs which belong to UNI(an , bn ) class has the following
performance guarantees:
( b /a )
n n −0.25(n−d)
εn = O n−1 , δn = e .
n/ ln n−d
e is asymptotically optimal if
So, A
n
bn /an ≤ , d = o(n).
ln n
The same result but for graphs with unlimited edges weights was presented in
e for graphs from classes EXP(an , αn ) and
[7], where presented analysis of algorithm A
On Algorithm for the k-MSTBB 13
e finds a solution with performance guarantees:
N(an , σn ). It is shown that A
( β /a )
n n
εn = O , δn = O(1/n).
n/ln n
Thus the algorithm is asymptotically optimal in the case then
βn ( n )
=o ,
an ln n
where βn = αn for the graphs from EXP(an , αn ) and σn in the case of N(an , σn ).
Another generalization of the MST problem is the problem of finding k edge-disjoint
spanning trees of a minimal total weight (k-MSTs). The k-MSTs is also polynomially
solvable, in [4] by Roskind and Tarjan was presented an algorithm with complexity
O(n2 log(n) + n2 k 2 ).
In current work a modification of the k-MSTs is considered where the aim is to
find k edge-disjoint spanning trees of a minimal total weight such that every tree has a
diameter not less than some predefined value d. We will call this problem as k minimum
spanning trees problem with diameter bounded below (k-MSTBB). It is NP-hard since
with dn = n − 1 and k = 1 it is equivalent to a problem of finding Hamiltonian Path
of a minimal weight in a given graph.
We propose a polynomial time algorithm to solve the k-MSTBB problem. The al-
gorithm builds k edge-disjoint Hamiltonian chains with d edges each on the preselected
set of d + 1 vertices. Then by the algorithm by Roskind and Tarjan [4] edge-disjoint
spanning trees in the number of k containing these chains are found. Also we present
performance guarantees of the algorithm and sufficient conditions of asymptotic opti-
mality for the graphs from UNI(an , bn ).
1 New algorithm Ak
Let us consider G = (V, E), an undirected complete n-vertex graph belonging to
UNI(an , bn ).
Our new algorithm is based on ideas of from [6], uses the algorithm by Roskind and
Tarjan [4] and algorithm AAV [1] which builds a Hamiltonian path in a given arbitrary
graph Gp with probability 1 − δAV .
Algorithm Ak :
1. Build k paths with a number of edges of d on the set of d + 1 vertices.
(a) Randomly remove all but d + 1 vertices from graph G, get G[d] inducted by
the set of vertices left.
(b) Build subgraphs G1 [d], ... , Gk [d] by a random procedure: every edge from G[d]
randomly gets one color between 1 and k.
(c) Remove all edges from G1 [d], ... , Gk [d] which weight more than some threshold
w, so we get graphs G1w [d], ... , Gkw [d].
(d) In G1w [d], ... , Gkw [d] find Hamiltonian paths by the algorithm AAV .
14 Edward Kh. Gimadi, Alexey M. Istomin, Ekaterina Yu. Shin
2. By the Roskind-Tarjan algorithm find k edges-disjoint spanning trees containing
paths built on the previous step.
Threshold value w must be chosen in a way that Giw [d] contains a Hamiltonian
path. In [2] it was established that on a d + 1 vertex graph where edge exists with a
probability p if the value of p is so that graph contains more than c(d + 1) log(d + 1)
edges, the graph will have a Hamiltonian path. In the paper [1] presented an algorithm
AAV to find such Hamiltonian path with high probability (whp) in O(d ln2 d) time.
Theorem 1. [1] For all α > 0 there exists a K(α) such that if the number of edges in
a random graph N > (α + K(α))(d + 1) ln(d + 1), where K(α) is sufficiently large, the
probability that algorithm AAV finds a Hamiltonian path is 1 − O(d−α ).
We will denote a threshold value of algorithm AAV as cAV = (α + K(α)). Now
let us formulate a Lemma to provide an estimation of probability that Giw [d] contains
enough edges for AAV to succeed.
Lemma 1. The probability that Giw [d] contains less than N edges is less than e−d if
p ≥ 4(N +d)
n(n−1) .
Proof.
∑
N −1 ( d(d−1) )
d(d−1)
δN = P r{Giw [d] contains less than N edges } = 2 pk (1 − p) 2 −k .
k
k=0
Now by the inequality
⌊(1−β)np⌋ ( )
∑ n k −β 2 np
p (1 − p)n−k ≤ e 2 .
k
k=0
which is correct for all n, p, β, where n is integer, p ∈ [0, 1] and β ∈ [0, 1], we get
d(d−1)
δ N ≤ e− 4 p+N
≤ e−d ,
if p ≥ 4(N +d)
d(d−1) .
Let’s denote δAV a probability of a case when the algorithm AAV was unable to
give us a solution: Giw [d] had not enough edges or algorithm AAV returned failure. By
Theorem 1 and Lemma 1
δAV = O(d−α + e−d ).
Let D˜n be a solution of the k-MSTBB found by algorithm Ak on a n-vertex graph.
By w0 we will denote a weight of solution of the k-MSTs. Now, let us formulate the
following Lemma.
Lemma 2. If all Ci , i ∈ {1, 2, . . . k}, were successfully built by the algorithm Ak , then
w(D˜n ) ≤ w0 + w(C1 ) + ... + w(Ck ) − kdan .
On Algorithm for the k-MSTBB 15
Proof. It is obvious that D˜n is a solution of the k-MSTs problem with a modified
weight function, if wij is an original weight of a edge (i, j) then modified one will be
∪
k
wij , if (i, j) ∈
/ Ct ,
′ t=1
wij =
∪
k
an , if ∈ Ct .
t=1
D˜n is a group of k edge-disjoint spanning trees with a minimum total weight among a
set Dn of all possible groups of k edge-disjoint spanning trees, where edges weights are
wij .
On the one hand we have:
∑ ∑
′ ′
min wij |Dn ∈ Dn = wij =
(i,j)∈Dn (i,j)∈D˜n
∑ ∑
′ ′
wij + ... + wij + w(D˜n ) − w(C1 ) − . . . − w(Ck ) =
(i,j)∈C1 (i,j)∈Ck
kdan + w(D˜n ) − w(C1 ) − . . . − w(Ck ).
′
On the other hand, since wij ≤ wij :
∑ ∑
′
min wij |Dn ∈ Dn ≤ min wij |Dn ∈ Dn =
(i,j)∈Dn (i,j)∈Dn
min {w(Dn )|Dn ∈ Dn } = w0 .
Combination of these two inequalities gives us the result of the Lemma.
Lemma 3. If Ci was successfully built by the algorithm Ak , then
w(Ci ) ≤ dan + 5kcAV (bn − an ) log d, i = 1, . . . , k,
where cAV is a threshold value defined for algorithm AAV by Theorem 1 [1].
Proof. Let i ∈ {1, . . . , k}. Let w be (bn − an )p + an , since edges weights have uniform
distribution on a segment [an , bn ] (we are considering graphs from class UNI(an , bn )),
the probability that an edge have weight less than w is equal to p. To grant to algorithm
AAV a possibility to find a Hamiltonian path graph Giw [d] must have more than cAV (d+
1) log(d + 1) edges. Together with Lemma 1 it means
log d
p ≤ 5kcAV .
d
It give us that every edge in Giw [d] has weight less than
log d
5kcAV (bn − an ) + an .
d
Ci contains d edges, so
w(Ci ) ≤ 5kcAV (bn − an ) log d + dan .
16 Edward Kh. Gimadi, Alexey M. Istomin, Ekaterina Yu. Shin
Theorem 2. Algorithm Ak has the following performance guarantees:
bn − an
εn = 5kcAV log d ,
an n
( ( ))
1 1
δn = O k + d ,
dα e
where cAV = (α + K(α)) is a constant, α > 0.
Proof. Let us first assume that we are under the condition that every Ci , i = 1, . . . , k,
was successfully found by the algorithm AAV . Using inequality knan ≤ w0 ≤ w(D˜n )
and Lemma 2 we have: { }
P r w(D˜n ) > (1 + εn )w∗ ≤
P r {w0 + w(C1 ) + ... + w(Ck ) − kdan > (1 + εn )w∗ } ≤
P r {w(C1 ) + ... + w(Ck ) − kdan > εn w∗ } ≤
P r {w(C1 ) + ... + w(Ck ) − kdan > εn knan } .
The last probability equals to zero since the inequality inside is always false due to the
definition of εn and Lemma 3 under the assumption that every Ci , i = 1, . . . , k, was
successfully found by the algorithm AAV .
A probability that Ci was successfully found is 1 − δAV , it give us the following
expression for the value of the failure probability of the algorithm Ak :
∏
k ∑
k ( ( ))
1 1
δn = 1 − (1 − δAV ) ≤ δAV = kδAV = O k + .
i=1 i=1
dα d
Theorem 3. The algorithm Ak is asymptotically optimal if d → ∞ as n → ∞, d =
o(n) and
bn /an = o(n/ log n).
Proof. It follows from the Theorem 2.
2 Conclusion
The problem of finding k minimum spanning trees with diameter bounded below was
studied. The polynomial algorithm was presented, its performance guarantees and suf-
ficient conditions of being asymptotically optimal were found for the case where edges
weights have independent uniform distribution on a segment [an , bn ], bn > an > 0.
Further analysis of this problem on graphs with other distributions of edges weights,
for example a case when an = 0, is of a big interest.
Acknowledgments. This research was supported by the Russian Foundation for Basic
Research (grants 15-01-00976 and 16-31-00389).
On Algorithm for the k-MSTBB 17
References
1. Angluin D.,Valiant L.G.: Fast probabilistic algorithms for Hamiltonian circuits and match-
ings. Journal of Computer and System Sciences, Vol 18(2), 155–193 (1979)
2. Erdos P., Renyi A.: On random graphs I, Publ. Math. Debrecen 6, 290–297, (1959)
3. Petrov V.V.: Limit Theorems of Probability Theory. Sequences of Independent Random
Variables. Clarendon Press, Oxford, 304 p., (1995)
4. Roskind J. and Tarjan R. E.: note on finding minimum-cost edge-disjoint spanning trees.
Math. Oper. Res., 10 (1985), 4, 701-708
5. Gimadi E.Kh., Glebov N.I., and Perepelitsa V.A.: Algorithms with Estimates for Discrete
Optimization Problems. Probl. Kibern., (1975), no. 31, pp. 35-42 (in Russian)
6. Gimadi E. Kh., Serdyukov A. I.: An algorithm for finding the minimum spanning tree with
a diameter bounded from below. Diskretn. Anal. Issled. Oper., Ser. 1, 7(2) (2000), 3-11 (in
Russian)
7. Gimadi E. Kh., Shin E. Yu.: Probabilistic analysis of an algorithm for the minimum span-
ning tree problem with diameter bounded below. Journal of Applied and Industrial Math-
ematics (October 2015), Volume 9, Issue 4, 480–488.