Back to Search
Start Over
Sublinear-time distributed algorithms for detecting small cliques and even cycles
- Source :
- Distributed Computing. 35:207-234
- Publication Year :
- 2021
- Publisher :
- Springer Science and Business Media LLC, 2021.
-
Abstract
- In this paper we give sublinear-time distributed algorithms in the CONGEST model for subgraph detection for two classes of graphs: cliques and even-length cycles. We show for the first time that all copies of 4-cliques and 5-cliques in the network graph can be listed in sublinear time, O(n^{5/6+o(1)}) rounds and O(n^{21/22+o(1)}) rounds, respectively. Prior to our work, it was not known whether it was possible to even check if the network contains a 4-clique or a 5-clique in sublinear time. For even-length cycles, C_{2k}, we give an improved sublinear-time algorithm, which exploits a new connection to extremal combinatorics. For example, for 6-cycles we improve the running time from O~(n^{5/6}) to O~(n^{3/4}) rounds. We also show two obstacles on proving lower bounds for C_{2k}-freeness: First, we use the new connection to extremal combinatorics to show that the current lower bound of Omega~(sqrt{n}) rounds for 6-cycle freeness cannot be improved using partition-based reductions from 2-party communication complexity, the technique by which all known lower bounds on subgraph detection have been proven to date. Second, we show that there is some fixed constant delta in (0,1/2) such that for any k, a Omega(n^{1/2+delta}) lower bound on C_{2k}-freeness implies new lower bounds in circuit complexity. For general subgraphs, it was shown in [Orr Fischer et al., 2018] that for any fixed k, there exists a subgraph H of size k such that H-freeness requires Omega~(n^{2-Theta(1/k)}) rounds. It was left as an open problem whether this is tight, or whether some constant-sized subgraph requires truly quadratic time to detect. We show that in fact, for any subgraph H of constant size k, the H-freeness problem can be solved in O(n^{2 - Theta(1/k)}) rounds, nearly matching the lower bound of [Orr Fischer et al., 2018].
- Subjects :
- Extremal combinatorics
000 Computer science, knowledge, general works
Matching (graph theory)
Computer Networks and Communications
Open problem
0102 computer and information sciences
01 natural sciences
Upper and lower bounds
Theoretical Computer Science
Combinatorics
03 medical and health sciences
0302 clinical medicine
Computational Theory and Mathematics
010201 computation theory & mathematics
Hardware and Architecture
030220 oncology & carcinogenesis
Computer Science
Partition (number theory)
Circuit complexity
Connection (algebraic framework)
Time complexity
Mathematics
Subjects
Details
- ISSN :
- 14320452 and 01782770
- Volume :
- 35
- Database :
- OpenAIRE
- Journal :
- Distributed Computing
- Accession number :
- edsair.doi.dedup.....9d056b61aae8a91dd51257fe0ec22577