Deterministic Distributed DFS and Other Problems via Cycle Separators in Planar Graphs
This work addresses the need for deterministic distributed algorithms in planar graphs, enabling derandomization of key algorithms like maximum flow and shortest paths, though it is incremental as it builds on existing separator techniques.
The authors tackled the problem of computing cycle separators in planar graphs within the distributed CONGEST model, presenting the first deterministic algorithm that achieves this in $ ilde{\mathcal{O}}(D)$ rounds, which matches the best-known randomized algorithm and leads to deterministic DFS tree computation and derandomization of other planar-graph algorithms.
One of the most basic techniques in algorithm design consists of breaking a problem into subproblems and then proceeding recursively. In the case of graph algorithms, one way to implement this approach is through separator sets. Given a graph $G=(V,E)$, a subset of nodes $S \subseteq V$ is called a separator set of $G$ if the size of each connected component of $G-S$ is at most $2/3 \cdot |V|$. The most useful separator sets are those that satisfy certain restrictions of cardinality or structure. For over 40 years, various efficient algorithms have been developed for computing separators of different kinds, particularly in planar graphs. Separator sets, combined with a divide and conquer approach, have been fundamental in the design of efficient algorithms in various settings. In this work, we present the first deterministic algorithm in the distributed CONGEST model that recursively computes a cycle separator in planar graphs in $\tilde{\mathcal{O}}(D)$ rounds. This result, as in the centralized setting, has significant implications for distributed planar algorithms. In fact, from this result, we can construct a deterministic algorithm that computes a DFS tree in $\tilde{\mathcal{O}}(D)$ rounds. This matches both the best-known randomized algorithm of Ghaffari and Parter (DISC'17) and, up to polylogarithmic factors, the trivial lower bound of $Ω(D)$ rounds. Besides DFS, our deterministic cycle separator algorithm can be used to derandomize several planar-graph algorithms whose only randomized ingredient is the computation of a cycle separator, such as maximum flow (Abd-Elhaleem, Dory, Parter and Weimann, PODC'25), single-source shortest path (Li and Parter, STOC'19), and reachability (Parter, DISC'20).