Distributed Triangle Enumeration in Hypergraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908842696114176 |
|---|---|
| author | Adamson, Duncan Rosenbaum, Will Spirakis, Paul G. |
| author_facet | Adamson, Duncan Rosenbaum, Will Spirakis, Paul G. |
| contents | In the last decade, subgraph detection and enumeration have emerged as a central problem in distributed graph algorithms. This is largely due to the theoretical challenges and practical applications of these problems. In this paper, we initiate the systematic study of distributed sub-hypergraph enumeration in hypergraphs. To this end, we (1)~introduce several computational models for hypergraphs that generalize the CONGEST model for graphs and evaluate their relative computational power, (2)~devise algorithms for distributed triangle enumeration in our computational models and prove their optimality in two such models, (3)~introduce classes of sparse and ``everywhere sparse'' hypergraphs and describe efficient distributed algorithms for triangle enumeration in these classes, and (4)~describe general techniques that we believe to be useful for designing efficient algorithms in our hypergraph models. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_17834 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Distributed Triangle Enumeration in Hypergraphs Adamson, Duncan Rosenbaum, Will Spirakis, Paul G. Distributed, Parallel, and Cluster Computing In the last decade, subgraph detection and enumeration have emerged as a central problem in distributed graph algorithms. This is largely due to the theoretical challenges and practical applications of these problems. In this paper, we initiate the systematic study of distributed sub-hypergraph enumeration in hypergraphs. To this end, we (1)~introduce several computational models for hypergraphs that generalize the CONGEST model for graphs and evaluate their relative computational power, (2)~devise algorithms for distributed triangle enumeration in our computational models and prove their optimality in two such models, (3)~introduce classes of sparse and ``everywhere sparse'' hypergraphs and describe efficient distributed algorithms for triangle enumeration in these classes, and (4)~describe general techniques that we believe to be useful for designing efficient algorithms in our hypergraph models. |
| title | Distributed Triangle Enumeration in Hypergraphs |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2602.17834 |