Eden, Talya ;
Fiat, Nimrod ;
Fischer, Orr ;
Kuhn, Fabian ;
Oshman, Rotem
SublinearTime Distributed Algorithms for Detecting Small Cliques and Even Cycles
Abstract
In this paper we give sublineartime distributed algorithms in the CONGEST model for subgraph detection for two classes of graphs: cliques and evenlength cycles. We show for the first time that all copies of 4cliques and 5cliques 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 4clique or a 5clique in sublinear time.
For evenlength cycles, C_{2k}, we give an improved sublineartime algorithm, which exploits a new connection to extremal combinatorics. For example, for 6cycles 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 6cycle freeness cannot be improved using partitionbased reductions from 2party 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 Hfreeness requires Omega~(n^{2Theta(1/k)}) rounds. It was left as an open problem whether this is tight, or whether some constantsized subgraph requires truly quadratic time to detect. We show that in fact, for any subgraph H of constant size k, the Hfreeness problem can be solved in O(n^{2  Theta(1/k)}) rounds, nearly matching the lower bound of [Orr Fischer et al., 2018].
BibTeX  Entry
@InProceedings{eden_et_al:LIPIcs:2019:11322,
author = {Talya Eden and Nimrod Fiat and Orr Fischer and Fabian Kuhn and Rotem Oshman},
title = {{SublinearTime Distributed Algorithms for Detecting Small Cliques and Even Cycles}},
booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)},
pages = {15:115:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771269},
ISSN = {18688969},
year = {2019},
volume = {146},
editor = {Jukka Suomela},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11322},
URN = {urn:nbn:de:0030drops113224},
doi = {10.4230/LIPIcs.DISC.2019.15},
annote = {Keywords: Distributed Computing, Subgraph Freeness, CONGEST}
}
08.10.2019
Keywords: 

Distributed Computing, Subgraph Freeness, CONGEST 
Seminar: 

33rd International Symposium on Distributed Computing (DISC 2019)

Issue date: 

2019 
Date of publication: 

08.10.2019 