Deterministic Lower Bounds for $k$-Edge Connectivity in the Distributed Sketching Model
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911432899035136 |
|---|---|
| author | Robinson, Peter Tan, Ming Ming |
| author_facet | Robinson, Peter Tan, Ming Ming |
| contents | We study the $k$-edge connectivity problem on undirected graphs in the distributed sketching model, where we have $n$ nodes and a referee. Each node sends a single message to the referee based on its 1-hop neighborhood in the graph, and the referee must decide whether the graph is $k$-edge connected by taking into account the received messages.
We present the first lower bound for deciding a graph connectivity problem in this model with a deterministic algorithm. Concretely, we show that the worst case message length is $Ω( k )$ bits for $k$-edge connectivity, for any super-constant $k = O(\sqrt{n})$. Previously, only a lower bound of $Ω( \log^3 n )$ bits was known for ($1$-edge) connectivity, due to Yu (SODA 2021). In fact, our result is the first super-polylogarithmic lower bound for a connectivity decision problem in the distributed graph sketching model.
To obtain our result, we introduce a new lower bound graph construction, as well as a new 3-party communication complexity problem that we call UniqueOverlap. As this problem does not appear to be amenable to reductions to existing hard problems such as set disjointness or indexing due to correlations between the inputs of the three players, we leverage results from cross-intersecting set families to prove the hardness of UniqueOverlap for deterministic algorithms. Finally, we obtain the sought lower bound for deciding $k$-edge connectivity via a novel simulation argument that, in contrast to previous works, does not introduce any probability of error and thus works for deterministic algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_11257 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Deterministic Lower Bounds for $k$-Edge Connectivity in the Distributed Sketching Model Robinson, Peter Tan, Ming Ming Data Structures and Algorithms Distributed, Parallel, and Cluster Computing We study the $k$-edge connectivity problem on undirected graphs in the distributed sketching model, where we have $n$ nodes and a referee. Each node sends a single message to the referee based on its 1-hop neighborhood in the graph, and the referee must decide whether the graph is $k$-edge connected by taking into account the received messages. We present the first lower bound for deciding a graph connectivity problem in this model with a deterministic algorithm. Concretely, we show that the worst case message length is $Ω( k )$ bits for $k$-edge connectivity, for any super-constant $k = O(\sqrt{n})$. Previously, only a lower bound of $Ω( \log^3 n )$ bits was known for ($1$-edge) connectivity, due to Yu (SODA 2021). In fact, our result is the first super-polylogarithmic lower bound for a connectivity decision problem in the distributed graph sketching model. To obtain our result, we introduce a new lower bound graph construction, as well as a new 3-party communication complexity problem that we call UniqueOverlap. As this problem does not appear to be amenable to reductions to existing hard problems such as set disjointness or indexing due to correlations between the inputs of the three players, we leverage results from cross-intersecting set families to prove the hardness of UniqueOverlap for deterministic algorithms. Finally, we obtain the sought lower bound for deciding $k$-edge connectivity via a novel simulation argument that, in contrast to previous works, does not introduce any probability of error and thus works for deterministic algorithms. |
| title | Deterministic Lower Bounds for $k$-Edge Connectivity in the Distributed Sketching Model |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2507.11257 |