TY - GEN
T1 - Deterministic Distributed DFS via Cycle Separators in Planar Graphs
AU - Jauregui, Benjamin
AU - Montealegre, Pedro
AU - Rapaport, Ivan
N1 - Publisher Copyright:
© 2025 Copyright is held by the owner/author(s). Publication rights licensed to ACM.
PY - 2025/6/13
Y1 - 2025/6/13
N2 - 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 ⊆ V is called a separator set of G if the size of each connected component of G - S is at most 2/3 · |V|. The most useful separator sets are those that satisfy certain restrictions of cardinality or structure.In this work, we present the first deterministic algorithm in the distributed CONGEST model that recursively computes a cycle separator over planar graphs in O(D) rounds. This result, as in the centralized setting, has significant implications in the area of distributed planar algorithms. In fact, from this result, we can construct a deterministic algorithm that computes a DFS tree in O(D) rounds. This matches both the best-known randomized algorithm of Ghaffari and Parter (DISC, 2017) and, up to polylogarithmic factors, the trivial lower bound of ω(D) rounds.
AB - 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 ⊆ V is called a separator set of G if the size of each connected component of G - S is at most 2/3 · |V|. The most useful separator sets are those that satisfy certain restrictions of cardinality or structure.In this work, we present the first deterministic algorithm in the distributed CONGEST model that recursively computes a cycle separator over planar graphs in O(D) rounds. This result, as in the centralized setting, has significant implications in the area of distributed planar algorithms. In fact, from this result, we can construct a deterministic algorithm that computes a DFS tree in O(D) rounds. This matches both the best-known randomized algorithm of Ghaffari and Parter (DISC, 2017) and, up to polylogarithmic factors, the trivial lower bound of ω(D) rounds.
KW - cycle separators
KW - depth-first search tree
KW - deterministic algorithms
KW - distributed graph algorithms
KW - planar graphs
KW - separator sets
UR - https://www.scopus.com/pages/publications/105026922544
U2 - 10.1145/3732772.3733558
DO - 10.1145/3732772.3733558
M3 - Conference contribution
AN - SCOPUS:105026922544
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 268
EP - 277
BT - PODC 2025 - Proceedings of the 2025 ACM Symposium on Principles of Distributed Computing
PB - Association for Computing Machinery
T2 - 44th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2025
Y2 - 16 June 2025 through 20 June 2025
ER -