Probabilistic Analysis of Optimization Problems on Generalized Random Shortest Path Metrics

A graph G=(V,E) satisfies the α,β-cut-property if the fraction of edges present in each cut of the graph lies between α and β. The Erdős-Rényi random graph G(n,p) satisfies this property w.h.p. for α=(1-ε)p and β=(1+ε)p whenever p is sufficiently large and ε is a suitably chosen constant.
We study the behavior of random shortest path metrics applied to graphs G that satisfy the α,β-cut-property. These random metrics are defined as follows: Let w(e) be independently drawn random edge weights for all e in E, and define d(u,v) to be the shortest path distance between u and v in G with respect to the weights w.
Using the ideas of Bringmann et al. (Algorithmica, 2015), who studied random shortest path metrics on the complete graph, i.e., the graph that satisfies the 1,1-cut-propertym we derive some properties of the metric and obtain a clustering of the vertices. Using this, we conduct a probabilistic analysis of some simple heuristics on these random shortest path metrics.