Abstract
In this paper we describe an algorithm that embeds a graph metric (V,d_G) on an undirected weighted graph G=(V,E) into a distribution of tree metrics (T,D_T) such that for every pair u,v in V, d_G(u,v)<=d_T(u,v) and E_T[d_T(u,v)]<=O(log n)d_G(u,v). Such embeddings have proved highly useful in designing fast approximation algorithms, as many hard problems on graphs are easy to solve on tree instances. For a graph with n vertices and m edges, our algorithm runs in O(m log n) time with high probability, which improves the previous upper bound of O(m log^3 n) shown by Mendel et al. in 2009.
The key component of our algorithm is a new approximate singlesource shortestpath algorithm, which implements the priority queue with a new data structure, the buckettree structure. The algorithm has three properties: it only requires linear time in terms of the number of edges in the input graph; the computed distances have the distance preserving property; and when computing the shortestpaths to the knearest vertices from the source, it only requires to visit these vertices and their edge lists. These properties are essential to guarantee the correctness and the stated work bound.
Using this shortestpath algorithm, we show how to generate an intermediate structure, the approximate dominance sequences of the input graph, in O(m log n) time, and further propose a simple yet efficient algorithm to converted this sequence to a tree embedding in O(n log n) time, both with high probability. Combining the three subroutines gives the stated work bound of the algorithm.
We also show a new application of probabilistic tree embeddings: they can be used to accelerate the construction of a series of approximate distance oracles.
BibTeX  Entry
@InProceedings{blelloch_et_al:LIPIcs:2017:7503,
author = {Guy E. Blelloch and Yan Gu and Yihan Sun},
title = {{Efficient Construction of Probabilistic Tree Embeddings}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {26:126:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7503},
URN = {urn:nbn:de:0030drops75034},
doi = {10.4230/LIPIcs.ICALP.2017.26},
annote = {Keywords: Graph Algorithm, Metric Embeddings, Probabilistic Tree Embeddings, Singlesource Shortestpaths}
}
Keywords: 

Graph Algorithm, Metric Embeddings, Probabilistic Tree Embeddings, Singlesource Shortestpaths 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) 
Issue Date: 

2017 
Date of publication: 

06.07.2017 