Reachability
Brief Announcement: Distributed Single-Source Reachability, [read] randomized, in $\tilde{O}(D+\sqrt{n}D^{1/4})$ rounds. Imporved from Distributed Approximation Algorithms for Weighted Shortest Paths which is $\tilde{O}(D+\sqrt{n}D^{1/2})$ rounds.
Parallel Reachability in Almost Linear Work and Square Root Depth, randomized, in $\tilde{O}(\sqrt{n}+n^{1/3+o(1)}D^{2/3})$ rounds.
Distributed Planar Reachability in Nearly Optimal Time, planer graph in $\tilde{O}(D)$ rounds.
Global minimum cut
[Ghaffari, Kuhn, 13]Distributed Minimum Cut Approximation.
Almost-Tight Distributed Minimum Cut Algorithms, [read], in $\tilde(O)(D+\sqrt{n})\lambda^4$ rounds where $\lambda$ is the edge connectivity.
Distributed Weighted Min-Cut in Nearly-Optimal Time, randomized, undirected, weighted, in $\tilde{O}(D+\sqrt{n})$ rounds.
Small Cuts and Connectivity Certificates: A Fault Tolerant Approach, for small cut and vertex cut.
Vertex Connectivity
Distributed connectivity decomposition, [read] Papers already read. Papers planning to read or currently reading. randomized, undirected, $O(\log n)$ approximation in $\tilde{O}(\sqrt{n}+D)$ rounds.
Max-Flow
Near-Optimal Distributed Maximum Flow. randomized, undirected, weighted $(1+\epsilon)$ approximate in $O(D+\sqrt{n})\cdot n^{o(1)}\cdot \epsilon^{-3}$ rounds.
Routing
Minimizing Congestion in General Networks. Optimal congestion routing for directed graphs.
Optimal Oblivious Routing in Polynomial Time. Linear programming to find optimal congest routing for both directed and undirected graph.
Distributed MST and Routing in Almost Mixing Time. [read]. Use random walk to do routing in expander graph. Application on MST and approximate Min-Cut.
Others
Distributed Verification and Hardness of Distributed Approximation
Near-Optimal Scheduling of Distributed Algorithms, [read].
Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut. Shortcut for planner graph and application in MST, approximate min-cut.
Universally-Optimal Distributed Algorithms for Known Topologies. [read] Supported congest model compute shortcut in tight running time $\tilde{O}(ShortCut(G))$.
Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model. [Censor-Hillel,Khoury,Paz,17]