Janson, Svante ;
Sorkin, Gregory B.
Successive Minimum Spanning Trees
Abstract
In a complete graph K_n with edge weights drawn independently from a uniform distribution U(0,1) (or alternatively an exponential distribution Exp(1)), let T_1 be the MST (the spanning tree of minimum weight) and let T_k be the MST after deletion of the edges of all previous trees T_i, i<k. We show that each tree's weight w(T_k) converges in probability to a constant gamma_k with 2k2 sqrt k < gamma_k < 2k+2 sqrt k, and we conjecture that gamma_k = 2k1+o(1). The problem is distinct from that of [Alan Frieze and Tony Johansson, 2018], finding k MSTs of combined minimum weight, and the combined cost for two trees in their problem is, asymptotically, strictly smaller than our gamma_1+gamma_2.
Our results also hold (and mostly are derived) in a multigraph model where edge weights for each vertex pair follow a Poisson process; here we additionally have E(w(T_k)) > gamma_k. Thinking of an edge of weight w as arriving at time t=n w, Kruskal's algorithm defines forests F_k(t), each initially empty and eventually equal to T_k, with each arriving edge added to the first F_k(t) where it does not create a cycle. Using tools of inhomogeneous random graphs we obtain structural results including that C_1(F_k(t))/n, the fraction of vertices in the largest component of F_k(t), converges in probability to a function rho_k(t), uniformly for all t, and that a giant component appears in F_k(t) at a time t=sigma_k. We conjecture that the functions rho_k tend to time translations of a single function, rho_k(2k+x) > rho_infty(x) as k > infty, uniformly in x in R.
Simulations and numerical computations give estimated values of gamma_k for small k, and support the conjectures stated above.
BibTeX  Entry
@InProceedings{janson_et_al:LIPIcs:2019:11275,
author = {Svante Janson and Gregory B. Sorkin},
title = {{Successive Minimum Spanning Trees}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {60:160:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771252},
ISSN = {18688969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11275},
URN = {urn:nbn:de:0030drops112759},
doi = {10.4230/LIPIcs.APPROXRANDOM.2019.60},
annote = {Keywords: miminum spanning tree, secondcheapest structure, inhomogeneous random graph, optimization in random structures, discrete probability, multitype bra}
}
17.09.2019
Keywords: 

miminum spanning tree, secondcheapest structure, inhomogeneous random graph, optimization in random structures, discrete probability, multitype bra 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Issue date: 

2019 
Date of publication: 

17.09.2019 