A Simple Distributed Deterministic Planar Separator
摘要
A balanced separator of a graph G is a set of vertices whose removal disconnects the graph into connected components that are a constant factor smaller than G. Lipton and Tarjan [FOCS’77] famously proved that every planar graph admits a balanced separator of size \(O(\sqrt{n})\) , as well as a balanced separator of size O(D) that is a simple path (where D is the graph’s diameter). In the centralized setting, these separators can both be found in linear O(n) time. In the distributed setting, since the diameter D is a trivial universal lower bound for the number of rounds required to solve many optimization problems, separators of size O(D) are preferable over those of size \(O(\sqrt{n})\) . It was not until [Ghaffari, Parter DISC’17] that an algorithm was devised to compute such an O(D)-size separator distributively in \(\tilde{O}(D)\) (The \(\tilde{O}(\cdot )\) notation is used to omit \(\text {poly}\log n\) factors.) rounds, by adapting the Lipton-Tarjan algorithm to the distributed model. Since then, this algorithm was used in several distributed algorithms for planar graphs, e.g., [Ghaffari, Parter DISC’17], [Li, Parter STOC’19], [Abd-Elhaleem, Dory, Parter and Weimann PODC’25]. However, the algorithm is randomized, deeming the algorithms that use it to be randomized as well. Obtaining a deterministic algorithm remained an interesting open question until very recently, when a (complex) deterministic separator algorithm was given by [Jauregui, Montealegre and Rapaport PODC’25]. In this paper, we present a much simpler deterministic separator algorithm with the same (near-optimal) \(\tilde{O}(D)\) -round complexity. While previous works devise either complicated or random ways of transferring weights from vertices of G to faces of G, we show that a straightforward way also works: Each vertex simply transfers its weight to one arbitrary face it belongs to. That’s it! We note that a deterministic separator algorithm directly derandomizes the state-of-the-art distributed algorithms for classical problems on planar graphs such as single-source shortest-paths, maximum-flow, directed global min-cut, and reachability.