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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Simple Distributed Deterministic Planar Separator

  • Yaseen Abd-Elhaleem,
  • Michal Dory,
  • Oren Weimann

摘要

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.