Yannic Maus

Kyungjin Cho, Michal Dory, Yannic Maus et al.

In this paper, we provide the first deterministic algorithms with sublogarithmic round complexity for spanners and approximate shortest paths in various MPC models. Moreover, we significantly improve upon the state of the art in the deterministic Congested Clique. In particular, we obtain the following four results on undirected graphs: 1. In both linear MPC and Congested Clique, we obtain an $O(k)$ stretch-spanner of a weighted graph of size $O(n^{1+1/k})$ in $O(1)$ rounds, for some parameter $k\ge 0$. For $k=O(\log{n})$, this leads to an $O(\log n)$ approximation of APSP in constant rounds in both models. 2. In sublinear MPC, we obtain an $O(k^{1+\varepsilon})$-stretch spanner of a weighted graph of size $O(n^{1+1/k})$ in $O(\log k)$ rounds, for any fixed constant $\varepsilon>0$. 3. In Congested Clique, we obtain $O(1)$-approximate APSP for weighted graphs in $O(\log \log \log n)$ rounds. 4. In near-linear MPC, we obtain $(1+\varepsilon)$-approximate single-source shortest paths and $O(1)$-approximate all-pairs shortest paths for unweighted graphs in $\textsf{poly}\log \log n$ rounds. Our algorithm only requires a single near-linear memory machine, where the rest can have sublinear memory. Our deterministic algorithms obtain similar guarantees to the state of the art randomized algorithms without incurring additional factors in the round complexity. To obtain these results, we inspect the randomized algorithms and isolate a randomized sampling routine. Then we derandomize these sampling routines by using a deterministic hitting set. Hereto, we develop a versatile deterministic hitting set algorithm, which we hope will have further derandomization applications.

Maxime Flin, Magnús M. Halldórsson, Manuel Jakob et al.

For any $Δ$, let $k_Δ$ be the maximum integer $k$ such that $(k+1)(k+2)\le Δ$. We give a distributed \LOCAL algorithm that, given an integer $k < k_Δ$, computes a valid $Δ-k$-coloring if one exists. The algorithm runs in $\tilde{O}(\log^4 \log n)$ rounds, which is within a polynomial factor of the $Ω(\log\log n)$ lower bound, which already applies to the case $k=0$. It is also best possible in the sense that if $k \ge k_Δ$, the problem requires $Ω(n/Δ)$ distributed rounds [Molloy, Reed, '14, Bamas, Esperet '19]. For $Δ$ at most polylogarithmic, the algorithm is an exponential improvement over the current state of the art of $O(\log^{49/12} n)$ rounds. When $Δ\ge (\log n)^{50}$, our algorithm achieves an even faster runtime of $O(\log^* n)$ rounds.

Malte Baumecker, Yannic Maus, Jara Uitto

Given a graph $G=(V,E)$, a $β$-ruling set is a subset $S\subseteq V$ that is i) independent, and ii) every node $v\in V$ has a node of $S$ within distance $β$. In this paper we present almost optimal distributed algorithms for finding ruling sets in trees and high girth graphs in the classic LOCAL model. As our first contribution we present an $O(\log\log n)$-round randomized algorithm for computing $2$-ruling sets on trees, almost matching the $Ω(\log\log n/\log\log\log n)$ lower bound given by Balliu et al. [FOCS'20]. Second, we show that $2$-ruling sets can be solved in $\widetilde{O}(\log^{5/3}\log n)$ rounds in high-girth graphs. Lastly, we show that $O(\log\log\log n)$-ruling sets can be computed in $\widetilde{O}(\log\log n)$ rounds in high-girth graphs matching the lower bound up to triple-log factors. All of these results either improve polynomially or exponentially on the previously best algorithms and use a smaller domination distance $β$.

Tijn de Vos, Leo Wennmann, Malte Baumecker et al.

In this paper, we consider the Santa Claus problem in the CONGEST model. This NP-hard problem can be modeled as a bipartite graph of children and gifts where an edge indicates that a child desires a gift. Notably, each gift can have a different value. The goal is to assign the gifts to the children such that the least happy child is as happy as possible. Even though this is a well-studied problem in the sequential setting, we obtain the first results the distributed setting. In particular, we show that the complexity of computing an $\mathcal{O}(\log n/\log \log n)$-approximation is $\hat Θ(\sqrt n+D)$ rounds, where our $\widetildeΩ(\sqrt n+D)$-round lower bound is even stronger and holds for any approximation.

Yannic Maus, Alexandre Nolin, Florian Schager

We obtain better algorithms for computing more balanced orientations and degree splits in LOCAL. Important to our result is a connection to the hypergraph sinkless orientation problem [BMNSU, SODA'25] We design an algorithm of complexity $\mathcal{O}(\varepsilon^{-1} \cdot \log n)$ for computing a balanced orientation with discrepancy at most $\varepsilon \cdot \mathrm{deg}(v)$ for every vertex $v \in V$. This improves upon a previous result by [GHKMSU, Distrib. Comput. 2020] of complexity $\mathcal{O}(\varepsilon^{-1} \cdot \log \varepsilon^{-1} \cdot (\log \log \varepsilon^{-1})^{1.71} \cdot \log n)$. Further, we show that this result can also be extended to compute undirected degree splits with the same discrepancy and in the same runtime. As as application we show that $(3 / 2 + \varepsilon)Δ$-edge coloring can now be solved in $\mathcal{O}(\varepsilon^{-1} \cdot \log^2 Δ\cdot \log n + \varepsilon^{-2} \cdot \log n)$ rounds in LOCAL. Note that for constant $\varepsilon$ and $Δ= \mathcal{O}(2^{\log^{1/3} n})$ this runtime matches the current state-of-the-art for $(2Δ- 1)$-edge coloring in [Ghaffari & Kuhn, FOCS'21].