Time-optimal construction of overlay networks

This article shows how to construct an overlay network of constant degree and diameter O(log n) in O(log n) time starting from an arbitrary weakly connected graph. We assume a synchronous communication network in which nodes can send messages to nodes they know the identifier of, and new connections can be established by sending node identifiers. Suppose the initial network's graph is weakly connected and has constant degree. In that case, our algorithm constructs the desired topology with each node sending and receiving only O(log n) messages in each round in O(log n) time w.h.p., which beats the currently best O(log3/2 n) time algorithm of Gotte et al. (International colloquium on structural information and communication complexity (SIROCCO), Springer, 2019). Since the problem cannot be solved faster than by using pointer jumping for O(log n) rounds (which would even require each node to communicate Q(n) bits), our algorithm is asymptotically optimal. We achieve this speedup by using short random walks to repeatedly establish random connections between the nodes that quickly reduce the conductance of the graph using an observation of Kwok and Lau (Approximation, randomization, and combinatorial optimization. Algorithms and techniques (APPROX/RANDOM 2014), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014). Additionally, we show how our algorithm can be used to efficiently solve graph problems in hybrid networks (Augustine et al. in Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, SIAM, 2020). Motivated by the idea that nodes possess two different modes of communication, we assume that communication of the initial edges is unrestricted, whereas only polylogarithmically many messages can be sent over edges that have been established throughout an algorithm's execution. For an (undirected) graph G with arbitrary degree, we show how to compute connected components, a spanning tree, and biconnected components in O(log n) time w.h.p. Furthermore, we show how to compute an MIS in O(log d + log log n) time w.h.p., where d is the initial degree of G.