Approximate Minimum Directed Spanning Trees Under Congestion

Abstract

The minimum directed spanning tree (MDST) problem has until recently not been studied in distributed computing models. This fundamental task generalizes the well-studied minimum spanning tree problem, by asking for a minimum weight spanning tree rooted at some specified node of a directed network. In their DISC 2019 paper [9], Fischer and Oshman reduce the MDST problem to the single-source shortest path (SSSP) problem, with a polylogarithmic increase in running time. This holds both in the Congest and Congested Clique models. Fischer and Oshman further suggest the possibility that an approximate SSSP algorithm could be leveraged in computing an approximate MDST. We extend their analysis to show that this is indeed the case: For $\epsilon >0$, using a $(1+\epsilon )$-approximation to SSSP running in $R$ rounds we can compute a $(1+\epsilon )$-approximate MDST in $\tilde{O}(R)$ rounds ($\tilde{O}$-notation neglects polylogarithmic factors in the number $n$ of nodes in the graph.). In particular, this implies the following improvements in the state of the art for $(1+o(1))$-approximation of MDST.

An $\tilde{O}(n^{1-2/\omega +o(1)})\subset \tilde{O}(n^{0.158})$-round Congested Clique algorithm, where $\omega <2.373$ is the fast matrix multiplication exponent [3].

An $\tilde{O}({\lambda }^2)$-round Congested Clique algorithm in graphs where each edge has an at most factor $\lambda \ge 1$ heavier reverse edge [1].

An $\tilde{O}({\lambda }^2(\sqrt{n}+D))$-round Congest algorithm in the same family of graphs [1]. For $\lambda \in {\log }^{O(1)}n$, the resulting running time of $\tilde{O}(\sqrt{n}+D)$ is unconditionally tight up to a polylogarithmic factor [21].