Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.18026 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909020659384320 |
|---|---|
| author | Yakunin, Alexander Kupavskii, Andrey Sushin, Alexander Moiseev, Stanislav |
| author_facet | Yakunin, Alexander Kupavskii, Andrey Sushin, Alexander Moiseev, Stanislav |
| contents | We study the problem of edge partitioning, where the goal is to partition the edge set of a graph into several parts. The replication factor of a vertex $v$ is the number of parts that contain edges incident to $v$. The goal is to minimize the average replication factor of the vertices while keeping the sizes of the parts nearly equal. We study the regime where the number of parts is significantly smaller than the size of the graph.
To this end, we introduce a new class of edge partitioning algorithms. These algorithms guarantee asymptotically worst-case-optimal upper bounds on the replication factor for any constant number of parts $k$, and when $k$ grows slowly with the number of vertices. In particular, we show that the optimal replication factor for growing $k$ is $\sqrt{k}(1+o(1))$.
The algorithms are computationally efficient, including in the LOCAL and CONGEST models, and can be implemented as stateless streaming algorithms in graph processing frameworks. Some of the worst-case graphs are complete graphs and jumbled graphs, also known as pseudo-random graphs.
Our method generalizes a family of algorithms based on symmetric intersecting families of sets. Informally, we replace the symmetry condition by a weaker balance condition that is still sufficient for the algorithms. This relaxation makes it possible to construct such families with asymptotically optimal rank $\sqrt{k}(1+o(1))$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_18026 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Near-optimal edge partitioning via intersecting families Yakunin, Alexander Kupavskii, Andrey Sushin, Alexander Moiseev, Stanislav Discrete Mathematics We study the problem of edge partitioning, where the goal is to partition the edge set of a graph into several parts. The replication factor of a vertex $v$ is the number of parts that contain edges incident to $v$. The goal is to minimize the average replication factor of the vertices while keeping the sizes of the parts nearly equal. We study the regime where the number of parts is significantly smaller than the size of the graph. To this end, we introduce a new class of edge partitioning algorithms. These algorithms guarantee asymptotically worst-case-optimal upper bounds on the replication factor for any constant number of parts $k$, and when $k$ grows slowly with the number of vertices. In particular, we show that the optimal replication factor for growing $k$ is $\sqrt{k}(1+o(1))$. The algorithms are computationally efficient, including in the LOCAL and CONGEST models, and can be implemented as stateless streaming algorithms in graph processing frameworks. Some of the worst-case graphs are complete graphs and jumbled graphs, also known as pseudo-random graphs. Our method generalizes a family of algorithms based on symmetric intersecting families of sets. Informally, we replace the symmetry condition by a weaker balance condition that is still sufficient for the algorithms. This relaxation makes it possible to construct such families with asymptotically optimal rank $\sqrt{k}(1+o(1))$. |
| title | Near-optimal edge partitioning via intersecting families |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2505.18026 |