The minimum spanning trees problem is to nd k edge-disjoint spanning trees in a given undirected weighted graph. It can be solved in polynomial time. In the k minimum spanning trees problem with diameter bounded below (k-MSTBB) there is an additional requirement: a diameter of every spanning tree must be not less than some prede ned value d. The k-MSTBB is N P hard. We propose an asymptotically optimal polynomial time algorithm to solve this problem.
Copyright ⃝c by the paper's authors. Copying permitted for private and academic purposes.
problem on the input I. According to [
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 ! 1.
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 p(x) = { 1 exp ( x an ); if an n n
x < 1; 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 cuttednormal distribution with a probability function p(x) = { p 2 2 n2 exp ( (x2 an2n)2 ); if an
x < 1; 0; otherwise.
In [
The algorithm Ae on graphs which belong to UNI(an; bn) class has the following performance guarantees: So, Ae is asymptotically optimal if "n = O ( bn=an ) n= ln nn d1 ; n = e 0:25(n d): n ln n bn=an
; d = o(n):
The same result but for graphs with unlimited edges weights was presented in
[
Another generalization of the MST problem is the problem of nding k edge-disjoint
spanning trees of a minimal total weight (k-MSTs). The k-MSTs is also polynomially
solvable, in [
In current work a modi cation of the k-MSTs is considered where the aim is to nd k edge-disjoint spanning trees of a minimal total weight such that every tree has a diameter not less than some prede ned 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 nding Hamiltonian Path of a minimal weight in a given graph.
We propose a polynomial time algorithm to solve the k-MSTBB problem. The
algorithm 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 [
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 [
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] nd Hamiltonian paths by the algorithm AAV . 2. By the Roskind-Tarjan algorithm paths built on the previous step.
nd k edges-disjoint spanning trees containing
Threshold value w must be chosen in a way that Giw[d] contains a Hamiltonian
path. In [
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 4n((Nn+1d)) .
Proof.
N = P rfGiw[d] contains less than N edges g = N∑1 ( d(dk2 1) )pk(1 d(d 1) k p) 2 : which is correct for all n; p; ; where n is integer, p 2 [0; 1] and 2 [0; 1], we get N e d(d4 1) p+N e d; if p
4d((Nd +1d)) .
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 2 f1; 2; : : : kg, were successfully built by the algorithm Ak, then w(D~n) w0 + w(C1) + ::: + w(Ck) kdan.
Now by the inequality
k=0 ⌊(1 )np⌋ (n)pk(1 ∑ k
k=0 p)n k
2np e 2 : Proof. It is obvious that D~n is a solution of the k-MSTs problem with a modi ed weight function, if wij is an original weight of a edge (i; j) then modi ed one will be 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:
8 min < ∑ ∑ (i;j)2C1 wi′j + : : : + :(i;j)2Dn
∑ (i;j)2Ck
9 wi′jjDn 2 Dn= =
; wi′j + w(D~n)
∑ (i;j)2D~n
wi′j = w(C1) : : :
w(Ck) = kdan + w(D~n) w(C1) : : : w(Ck): On the other hand, since wi′j
wij: 8 min < ∑ :(i;j)2Dn wi′jjDn 2 Dn 9 = ;
8 min < ∑ :(i;j)2Dn
9 wijjDn 2 Dn= =
;
min fw(Dn)jDn 2 Dng = 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 de ned for algorithm AAV by Theorem 1 [
+ an: w(Ci) 5kcAV (bn
an) log d + dan: p 5kcAV log d d
: log d d Theorem 2. Algorithm Ak has the following performance guarantees: "n = 5kcAV log d bn n = O ( ( 1 k
+ d > 0.
an ann 1 )) ed ; ; where cAV = ( + K( )) is a constant, Proof. Let us rst 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 fw0 + w(C1) + ::: + w(Ck)
kdan > (1 + "n)w g P r fw(C1) + ::: + w(Ck)
kdan > "nw g P r fw(C1) + ::: + w(Ck) kdan > "nknang : The last probability equals to zero since the inequality inside is always false due to the de nition 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: Theorem 3. The algorithm Ak is asymptotically optimal if d ! 1 as n ! 1, d = o(n) and
bn=an = o(n= log n): Proof. It follows from the Theorem 2. 2
The problem of nding k minimum spanning trees with diameter bounded below was studied. The polynomial algorithm was presented, its performance guarantees and sufcient 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).