Virginia Vassilevska Williams

Jakob Nogler, Virginia Vassilevska Williams

Given a graph and two fixed vertices $s$ and $t$, the Replacement Path Problem (RP) is to compute for every edge $e$, the distance between $s$ and $t$ when $e$ is removed. There are two natural extensions to RP: (1) Single Source Replacement Paths (SSRP): Given a graph $G$ and a source node $s$, compute for every vertex $v$ and every edge $e$ the $s$-$v$ distance in $G \setminus \{e\}$. That is, we do not fix the target anymore. (2) $2$-Fault Replacement Paths (2-FRP): Given a graph $G$ and two nodes $s$ and $t$, compute for every pair of edges $e, e'$ the $s$-$t$ distance in $G \setminus \{e, e'\}$. That is, we consider two failures instead of one. Previously, there was no known reduction between SSRP and 2-FRP. It seemed plausible that 2-FRP would be computationally harder because there are no settings where 2-FRP admits a faster algorithm than SSRP. In directed unweighted graphs there is a provable gap in complexity, and in undirected graphs many of the known 2-FRP algorithms in a variety of settings are much slower than those for SSRP in the same setting. The main contribution of this paper is a tight reduction from undirected $2$-FRP to undirected SSRP, showing that contrary to prior intuition, 2-FRP is not harder than SSRP. As our reduction is weight-preserving, we obtain the first algorithms for $2$-FRP that match the best-known runtimes for SSRP: (1) $\tilde{O}(M n^ω)$ for weights in $[1, M]$ [GVW19], improving upon $O(Mn^{2.87})$ [CZ24]; (2) $n^3/2^{Ω(\sqrt{\log n})}$ for weights in $[1, \text{poly}(n)]$ [GVW19], improving over the previous $n^3\text{polylog}(n)$ running time [VWWX22]; (3) $\tilde{O}(mn^{1/2}+n^{2})$ combinatorial time for unweighted graphs [CC19], and more generally for rational weights in $[1, 2]$ [CM20], improving upon $\tilde{O}(n^{3-1/18})$ [CZ24]. We complement these upper bounds with tight lower bounds under fine-grained hypotheses.

Yael Kirkpatrick, Liam Roditty, Richard Qi et al.

Computing the diameter of a graph is a problem of great interest both in general algorithms research and specifically within fine-grained complexity, where it is a cornerstone hard problem. Recent work has achieved a full conditional lower bound tradeoff curve for both directed and undirected graphs. However, the best known upper bounds do not match the lower bounds. In particular, the best known approximation scheme for undirected graph diameter has not been improved. Moreover, this scheme is randomized and no similar deterministic scheme is known. Another fundamental field of research in shortest paths computation is the construction of approximate distance oracles. Thorup and Zwick [JACM'05] provided the first such distance oracle with constant query time and (conditionally) optimal space, and in the years since many advances have led to a vast toolbox of techniques and data structures. These two areas of research seem natural to combine since they both concern approximating shortest paths. However, the known diameter approximation algorithms only use a small subset of the techniques used in distance oracles research. In this work we show that in fact approximate diameter and distance oracles are intricately connected. We first demonstrate a strong connection between the current best known diameter approximation scheme of Cairo, Grossi and Rizzi ("CGR") and the $(2k-1)$-approximate distance oracle of Thorup and Zwick. This allows us to derandomize the CGR algorithm and obtain the first deterministic diameter approximation tradeoff. We further derandomize other central techniques in the field of distance oracles and use them to achieve new deterministic diameter approximation algorithms. Finally, we show how these new techniques can be used to derandomize many current best known results in various fields of shortest paths approximations.

Krzysztof Sornat, Virginia Vassilevska Williams, Yinzhan Xu

We study computational aspects of a well-known single-winner voting rule called the Schulze method [Schulze, 2003] which is used broadly in practice. In this method the voters give (weak) ordinal preference ballots which are used to define the weighted majority graph (WMG) of direct comparisons between pairs of candidates. The choice of the winner comes from indirect comparisons in the graph, and more specifically from considering directed paths instead of direct comparisons between candidates. When the input is the WMG, to our knowledge, the fastest algorithm for computing all winners in the Schulze method uses a folklore reduction to the All-Pairs Bottleneck Paths problem and runs in $O(m^{2.69})$ time, where $m$ is the number of candidates. It is an interesting open question whether this can be improved. Our first result is a combinatorial algorithm with a nearly quadratic running time for computing all winners. This running time is essentially optimal. If the input to the Schulze winners problem is not the WMG but the preference profile, then constructing the WMG is a bottleneck that increases the running time significantly; in the special case when there are $m$ candidates and $n=O(m)$ voters, the running time is $O(m^{2.69})$, or $O(m^{2.5})$ if there is a nearly-linear time algorithm for multiplying dense square matrices. To address this bottleneck, we prove a formal equivalence between the well-studied Dominance Product problem and the problem of computing the WMG. We prove a similar connection between the so called Dominating Pairs problem and the problem of finding a winner in the Schulze method. Our paper is the first to bring fine-grained complexity into the field of computational social choice. Using it we can identify voting protocols that are unlikely to be practical for large numbers of candidates and/or voters, as their complexity is likely, say at least cubic.