PBS is proposed and analyzed, a simple sublinear approximation algorithm for power-law graphs with parameter $\beta\in[2,3)$ that does not require any preprocessing, yet exhibits performance comparable to light index-based algorithms (of linear or sublinear index size).
Abstract
Computing shortest paths in large graphs is, and remains, a fundamental and practically motivated problem. While many algorithms were proposed to calculate shortest path between pairs of vertices efficiently, many of them (index-based methods) require substantial preprocessing, while others (traversal-based methods) have higher time complexity. In this paper, we propose and analyze Pruned Bidirectional Search (PBS), a simple sublinear approximation algorithm for power-law graphs with parameter $\beta\in[2,3)$: our algorithm does not require any preprocessing, yet exhibits performance comparable to light index-based algorithms (of linear or sublinear index size): that is, PBS runs in time $O(n^{(1-1/\log\log n)/2})$ and, with high probability, returns a path with length within $\frac{41}{32}$ of the shortest path. Moreover, if one does allow a $n^{\Theta(2-1/\log\log n)}$-time preprocessing step, its query time improves to $n^{\Theta(1/\log\log n})$. We complement our theoretical results by experiments on both real-world and synthetic power-law graphs, which show that PBS is typically $1.84\times$-$7.76\times$ times faster than existing alternatives, while achieving an approximation ratio at most 1.05.
Given an undirected, unweighted graph $G$, we aim to compute a 2-approximation of all-pairs shortest paths (APSP). This problem admits a natural lower bound of $\Omega(n^2)$ since the output size is $\Theta(n^2)$. A central goal in this area is to achieve a running time of $O(n^2)$. Dor, Halperin, and Zwick (FOCS 1996, SICOMP 2001) designed an algorithm with a running time of $\tilde{O}(n^2)$ that guarantees a 2-approximation only for pairs at a distance of at least $O(\log n)$. Recently, Gupta (FOCS 2025) improved this bound, handling all pairs at a distance of at least $O(\log \log n)$. We nearly resolve this problem. We design a randomized algorithm that runs in $\tilde{O}(n^2)$ time and, with high probability, guarantees a 2-approximation for all pairs at distance at least $c$, where $c \ge 0$ is a constant. Unlike the above two results, which were purely combinatorial, our algorithm combines combinatorial techniques with fast matrix multiplication (FMM).
We revisit several fundamental graph problems in the deterministic two-party communication model. Our main contributions include: (1) a new $\widetilde{O}(n^{3/2})$-bit protocol for computing a maximum matching in general graphs. While the same upper bound can be obtained by simulating the classic algorithms of Micali-Vazirani and Gabow, our protocol is conceptually simple and avoids the intricacies of finding a maximal set of shortest augmenting paths; (2) a new $\widetilde{O}(n)$-bit protocol for negative-cycle detection and negative-weight single-source shortest paths. Our protocol simplifies that of Blikstad et al. by replacing a long chain of reductions with a more direct approach based on vertex potentials; (3) a combinatorial $\widetilde{O}(n)$-bit protocol for computing a maximum matching in bipartite graphs, obtained by reinterpreting the near-linear communication protocol of Blikstad et al. through a discretized analysis. Together, these results provide simpler protocols for several basic graph problems. We hope they will inspire further advances on the communication complexity of a wide range of graph problems.
Yu Cheng, Tianle Jiang, Pachara Sawettamalya et al.· 0 citations
In the (fully) dynamic edge connectivity problem, the goal is to maintain the edge connectivity $\lambda_G$ of an $n$-vertex graph $G$ that undergoes edge insertions and deletions. Our main result is a randomized algorithm for maintaining edge connectivity in dynamic simple graphs using worst-case update and query time $\tilde{O}(n^{12/13})$, for all values of $\lambda_G$. This is the first algorithm that has $o(n)$ update and query time, as all existing algorithms achieve this only when $\lambda_G$ is below $n^{1/11}$ or above $n^{1/2}$ (up to polylogarithmic factors). We then use the tools developed for this purpose to design two additional algorithms. The first one is a deterministic algorithm for the exact same task, that uses $n^{1+o(1)}$ worst-case update and query time or $\tilde{O}(n)$ amortized update and query time; this gives a polynomial improvement over existing deterministic algorithms. The second one is a deterministic algorithm for the same task but in dynamic unweighted multigraphs, that uses $\tilde{O}(n^{3/2})$ worst-case update and query time.
Yotam Kenneth-Mordoch, Robert Krauthgamer· 0 citations
The first $poly(\Delta,\log n)-round algorithm for $(\Delta + 1)$-edge coloring in the CONGEST model is presented and the $n$-dependency of its runtime, $\tilde{O}(\log^5 n)$, matches the best published dependency in the LOCAL model.
Sebastian Brandt, Ananth Narayanan, Alexandre Nolin· 0 citations
For every $\varepsilon>0$, it is NP-hard to $n^{1-\varepsilon}$-approximate Max Independent Set in $n$-vertex graphs [Hastad'96, Zuckerman'07]. In triangle-free graphs, a simple argument gives a polynomial-time $n^{1/2}$-approximation algorithm, whereas, for every $\varepsilon>0$, an $n^{1/4-\varepsilon}$-approximation algorithm would imply that NP $\subseteq$ BPP [Bonnet, Thomass\'e, Tran, Watrigant; ESA'20]. In this note, we close this gap by proving the corresponding hardness against $n^{1/2-\varepsilon}$-approximation algorithms. The reduction is very simple and uses the Moser-Tardos resampling algorithm to make the constructed graphs triangle-free. The soundness uses a result of Haeupler, Saha, and Srinivasan building on the proof of Moser and Tardos, to upper-bound the probability that a fixed relatively large subset is an independent set after the Moser-Tardos algorithm terminates. We generalize this scheme and show that, for any nonempty finite family $\mathcal F$ of graphs, each containing at least one cycle, for any $\varepsilon>0$, an $n^{\mu(\mathcal F)-\varepsilon}$-approximation algorithm for Max Independent Set in graphs excluding every member of $\mathcal F$ as a subgraph implies that NP $\subseteq$ BPP, where $\mu(\mathcal F) := 1 - \max\limits_{H \in \mathcal F}~\min\limits_{U \subseteq V(H), H[U] \text{contains a cycle}} (|U|-2)/(|E(H[U])|-1)$.
We study the problem of approximating the diameter of directed graphs under the min-distance measure, defined as $d_{\min}(u,v) = \min(d(u,v), d(v,u))$. Unlike standard shortest-path distance, min-distance is not a metric, which renders many classical techniques inapplicable. Prior work has therefore focused on approximating this parameter, culminating in an approximation-runtime tradeoff by Dalirrooyfard et al. [ICALP'19] giving a $4k-1$ approximation in $\tilde{O}(mn^{1/(k+1)})$ time for any positive integer $k$ and, more recently, the first near-linear time constant approximation by Chechik and Zhang [FOCS'22], where they obtained a 4-approximation to the min-diameter. In this work we present a randomized near-linear time algorithm that achieves a $3$-approximation to the min-diameter, outperforming all known approximation-runtime tradeoffs. Our approach introduces a novel type-classification framework that may be of independent interest. We further extend our techniques to the more general setting of multimode graphs, recently introduced as a generalization of min-distance by Kirkpatrick and Vassilevska W. [MFCS'25]. For directed $2$-mode graphs, we obtain a $3$-approximation to the diameter in near-linear time, dramatically improving over the previously best known $n$-approximation. Our results significantly narrow the gap between min-distance and multimode distance approximations, and open new directions for understanding graph parameters under non-metric distance measures.