Approximate Minimum Directed Spanning Trees under Congestion

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 \varepsilon >0, using a (1+\varepsilon)-approximation to SSSP running in R rounds we can compute a (1+\varepsilon )-approximate MDST in \tilde{O}(R) rounds.\footnote{$\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.

--------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.