Approximate Minimum Directed Spanning Tree in Congest and Congested Clique Models (Master's Thesis)

In this work, we study MDST approximation in the distributed setting. We confirm the above conjecture of Fischer and Oshman by analyzing the use of the approximate SSSP algorithm. We generalize the framework by Fischer and Oshman and show that approximate MDST can be solved in \tilde{O}(T) rounds in Congest and Congested Clique models, where \tilde{O} notation hides polylogarithmic factors and, T is the running time of (1+\varepsilon)-approximate SSSP in the respective models. Applying the state-of-the-art approximate SSSP algorithms to the above result yield the following.
- \tilde{O}(n^{1-2/\omega+o(1)})-round Congested Clique algorithm, where \omega<2.373 is the fast matrix multiplication exponent.
- \tilde{O}( (\sqrt{n}D^{1/4}+D)/\varepsilon )-round Congest algorithm.