Liam Roditty

Avi Kadria, Liam Roditty

Let $G=(V, E)$ be an undirected $n$-vertices $m$-edges graph with non-negative edge weights. In this paper, we present three new algorithms for constructing a $(2k-1)$-stretch distance oracle with $O(n^{1+\frac{1}{k}})$ space. The first algorithm runs in $\Ot(\max(n^{1+2/k}, m^{1-\frac{1}{k-1}}n^{\frac{2}{k-1}}))$ time, and improves upon the $\Ot(\min(mn^{\frac{1}{k}},n^2))$ time of Thorup and Zwick [STOC 2001, JACM 2005] and Baswana and Kavitha [FOCS 2006, SICOMP 2010], for every $k > 2$ and $m=Ω(n^{1+\frac{1}{k}+\eps})$. This yields the first truly subquadratic time construction for every $2 < k < 6$, and nearly resolves the open problem posed by Wulff-Nilsen [SODA 2012] on the existence of such constructions. The two other algorithms have a running time of the form $\Ot(m+n^{1+f(k)})$, which is near linear in $m$ if $m=Ω(n^{1+f(k)})$, and therefore optimal in such graphs. One algorithm runs in $\Ot(m+n^{\frac32+\frac{3}{4k-6}})$-time, which improves upon the $\Ot(n^2)$-time algorithm of Baswana and Kavitha [FOCS 2006, SICOMP 2010], for $3 < k < 6$, and upon the $\Ot(m+n^{\frac{3}{2}+\frac{2}{k}+O(k^{-2})})$-time algorithm of Wulff-Nilsen [SODA 2012], for every $k\geq 6$. This is the first linear time algorithm for constructing a $7$-stretch distance oracle and a $9$-stretch distance oracle, for graphs with truly subquadratic density.\footnote{with $m=n^{2-\eps}$ for some $\eps > 0$.} The other algorithm runs in $\Ot(\sqrt{k}m+kn^{1+\frac{2\sqrt{2}}{\sqrt{k}}})$ time, (and hence relevant only for $k\ge 16$), and improves upon the $\Ot(\sqrt{k}m+kn^{1+\frac{2\sqrt{6}}{\sqrt{k}}+O(k^{-1})})$ time algorithm of Wulff-Nilsen [SODA 2012] (which is relevant only for $k\ge 96$). ...

Hodaya Barr, Yohai Trabelsi, Sarit Kraus et al.

In many settings, there is an organizer who would like to divide a set of agents into $k$ coalitions, and cares about the friendships within each coalition. Specifically, the organizer might want to maximize utilitarian social welfare, maximize egalitarian social welfare, or simply guarantee that every agent will have at least one friend within his coalition. However, in many situations, the organizer is not familiar with the friendship connections, and he needs to obtain them from the agents. In this setting, a manipulative agent may falsely report friendship connections in order to increase his utility. In this paper, we analyze the complexity of finding manipulation in such $k$-coalitional games on graphs. We also introduce a new type of manipulation, socially-aware manipulation, in which the manipulator would like to increase his utility without decreasing the social welfare. We then study the complexity of finding socially-aware manipulation in our setting. Finally, we examine the frequency of socially-aware manipulation and the running time of our algorithms via simulation results.

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.

Liam Roditty, Ariel Sapir

We introduce a generalized family of $\left( 2\cdot \left\lfloor \frac{k}{2} \right\rfloor-1, 2\cdot \left\lceil \frac{k}{2} \right\rceil \cdot W_{1} +\max\left\{0,2\cdot\left(\left\lceil\frac{k}{2}\right\rceil-2\right)\right\}\cdot W_{2} \right)$-emulators with $\tilde O \left(n^{1+\frac{1}{k}}\right)$ edges, for any $k\in\mathbb{N}$, where $W_{i}$ is the $i$th heaviest edge on a shortest path between two vertices. Our construction generalizes the $+2W_{1}$-spanner of size $\tilde O\left(n^{\frac{3}{2}}\right)$ and the $+4W_{1}$-emulator of size $\tilde O \left(n^{\frac{4}{3}}\right)$, both by Elkin, Gitlitz and Neiman [DISC'21 and DICO'23]. When $k$ is even, these are $\left(k-1,k\cdot W_{1} + \left(k-4\right)\cdot W_{2}\right)$-emulators and when $k$ is odd, these are $\left(k-2,\left(k+1\right)\cdot W_{1} + \left(k-3\right) \cdot W_{2}\right)$-emulators. Our framework not only expands known constructions for weighted graphs but also yields an improved stretch over state of the art emulators and spanners for unweighted graphs within a specific distance regime. In particular, for all vertex pairs separated by a distance of $δ\leq O\left(3^{k^{2}}\right)$, our construction improves upon the seminal additive $+\tilde O\left(δ^{1-\frac{1}{k}}\right)$-emulator of size $\tilde O\left(n^{1+\frac{1}{2^{k+1}-1}}\right)$ by Thorup and Zwick [SODA'06].