Quantum
Quantum query complexity of some graph problems
Approximate k-spanner
Approximating k-Spanner Problems for k > 2 bicriteria approximation
Transitive-Closure Spanners: A Survey, two interesting papers: Transitive-Closure Spanners, Finding Sparser Directed Spanners
On the Hardness of Approximating Spanners Hardness of MIN-REP
The Hardness of Approximating Spanner Problems hardness result for many settings (directed), reduction to MIN-REP
Approximating Low-Stretch Spanners improvements on $k=4$
Approximation algorithms for spanner problems and Directed Steiner Forest for any $k$
Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner hardness for undirected
Directed Spanners via Flow-Based Linear Programs
Matching
[Assadi, Jambulapati, Jin, Sidford, Tian, SODA'22] Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space, using [Cohen, Sidford, Tian, ITCS'21] Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration and [Jambulapati, Liu, Sidford, FOCS'19] A Direct $\tilde{O}(1/\epsilon)$ Iteration Parallel Algorithm for Optimal Transport
[Ahn, Guha, 18] Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching under Resource Constraints
[Ahmadi, Kuhn, Oshman, DISC'18] Distributed Approximate Maximum Matching in the CONGEST Model
String Sketching
Improved sketching of hamming distance with error correcting [Porat, Lipsky, CPM'07]
Connectivity
Vertex Sampling and Vertex Connectivity
[Censor-Hillel, Ghaffari, Kuhn, SODA'14] A New Perspective on Vertex Connectivity, sampling with probability $p$ leads to $\Omega(kp^2/\log^3 n)$ connected.
[ Censor-Hillel, Ghaffari, Giakkoupis, Haeupler, Kuhn, SODA'15] Tight Bounds on Vertex Connectivity Under Vertex Sampling, improved to $\Omega(kp^2)$, which is optimal.
Vetex Connectivity Oracles
[Pettie, Yin, ICALP'21] The Structure of Minimum Vertex Cuts
[Pettie, Saranurak, Yin, STOC'22] Optimal Vertex Connectivity Oracles
Cut Query
[Rubinstein, Schramn, Weinberg, ITCS'18] Computing exact minimum cuts without knowing the graph
[Mukhopadhyay, Nanongkai, STOC'20] Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms
Reachability
Streaming Lower Bound
[Chen, Kol, Paramonov, Saxena, Song, Yu, STOC'21] Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability
[Assadi, Raz, FOCS'20] Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms
[Guruswami, Onak, CCC'13] Superlinear lower bounds for multipass graph processing
[Assadi, Chen, Khanna, STOC'19] Polynomial Pass Lower Bounds for Graph Streaming Algorithms
Parallel
[Fineman, STOC'18] Nearly Work-Efficient Parallel Algorithm for Digraph Reachability
[Jambulapati, Liu, Sidford, STOC'19] Parallel Reachability in Almost Linear Work and Square Root Depth
[Cao, Fineman, Russell, SPAA'20] Brief Announcement: Improved Work Span Tradeoff for Single Source Reachability and Approximate Shortest Paths
CONGEST
[Nanongkai, STOC'14] Distributed Approximation Algorithms for Weighted Shortest Paths, $\tilde{O}(D+\sqrt{n}D^{1/2})$ rounds.
[Ghaffari, Udwani, PODC'15] Brief Announcement: Distributed Single-Source Reachability, $\tilde{O}(D+\sqrt{n}D^{1/4})$ rounds.
[Jambulapati, Liu, Sidford, STOC'19] Parallel Reachability in Almost Linear Work and Square Root Depth , $\tilde{O}(\sqrt{n}+n^{1/3+o(1)}D^{2/3})$ rounds.
[Parter, DISC'20] Distributed Planar Reachability in Nearly Optimal Time, planer graph in $\tilde{O}(D)$ rounds.
Diameter-Reducing Shortcuts
[Kogan, Parter, SODA'22] New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the O(√n) Barrier
[Huang, Pettie, 18] Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing Shortcuts
[Hesse, SODA'03] Directed graphs requiring large numbers of shortcuts.
Max-Flow
CONGEST
[Ghaffari, Karrenbauer, Kuhn, Lenzen, Patt-Shamir, PODC'15]. Near-Optimal Distributed Maximum Flow randomized, undirected, weighted, $(1+\epsilon)$ approximate in $O(D+\sqrt{n})\cdot n^{o(1)}\cdot \epsilon^{-3}$ rounds.
[Forster, Goranci, Liu, Peng, Sun, Ye, FOCS'21], Minor Sparsifiers and the Distributed Laplacian Paradigm.
[Anagnostides, Lenzen, Haeupler, Zuzic, Gouleakis], Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts.
Sequential
[Cohen, Madry, Sankowski, Vladu, SODA'17] Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in $\tilde{O}(m^{10/7}\log W)$ time.
[vdBLNPSSSW, FOCS'20] Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs.
[vdBLLSSSW, SOTC'20] Minimum Cost Flows, MDPs, and $\ell_1$-Regression in Nearly Linear Time for Dense Instances.
[Chen, Kyng, Liu, Peng, Gutenberg, Sachdeva, FOCS'22] Maximum Flow and Minimum-Cost Flow in Almost-Linear Time.
Misc.
[Chekuri, Quanrud, ICALP'21] Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Global Connectivity Problems
[Li, Nanongkai, Panigrahi, Saranurak] Fair Cuts, Approximate Isolating Cuts, and Approximate Gomory-Hu Trees in Near-Linear Time
[Ghaffari, Kuhn, Su, PODC'17] Distributed MST and Routing in Almost Mixing Time