Czumaj, Artur and Konrad, Christian (2018) Detecting cliques in CONGEST networks. In: 32nd International Symposium on Distributed Computing (DISC 2018), New Orleans, LA, 15-19 Oct 2018. Published in: 32nd International Symposium on Distributed Computing (DISC 2018), 121 16:1-16:15. ISBN 9783959770927. doi:10.4230/LIPIcs.DISC.2018.16 ISSN 1868-8969.

Preview

PDF WRAP-detecting-cliques-CONGEST-networks-Czumaj-2018.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (618Kb) | Preview

Request Changes to record.

Abstract

The problem of detecting network structures plays a central role in distributed computing. One of the fundamental problems studied in this area is to determine whether for a given graph H, the input network contains a subgraph isomorphic to H or not. We investigate this problem for H being a clique K_s in the classical distributed CONGEST model, where the communication topology is the same as the topology of the underlying network, and with limited communication bandwidth on the links.

Our first and main result is a lower bound, showing that detecting K_s requires Omega(sqrt(n)/b) communication rounds, for every 4 \le s \le sqrt(n), and Omega(n/(sb)), where b is the bandwidth of the communication links. This result is obtained by using a reduction to the set disjointness problem in the framework of two-party communication complexity. We complement our lower bound with a two-party communication protocol for listing all cliques in the input graph, which up to constant factors communicates the same number of bits as our lower bound for K_4 detection. This demonstrates that our lower bound cannot be improved using the two-party communication framework.

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH):	Electronic data processing -- Distributed processing, Algorithms
Series Name:	Leibniz International Proceedings in Informatics (LIPIcs)
Journal or Publication Title:	32nd International Symposium on Distributed Computing (DISC 2018)
Publisher:	Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
ISBN:	9783959770927
ISSN:	1868-8969
Official Date:	4 October 2018
Dates:	Date Event 4 October 2018 Published 19 July 2018 Accepted
Volume:	121
Page Range:	16:1-16:15
DOI:	10.4230/LIPIcs.DISC.2018.16
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Open Access (Creative Commons)
Date of first compliant deposit:	17 August 2018
Date of first compliant Open Access:	17 August 2018
RIOXX Funder/Project Grant:	Project/Grant ID RIOXX Funder Name Funder ID EP/D063191/1 [EPSRC] Engineering and Physical Sciences Research Council http://dx.doi.org/10.13039/501100000266 EP/N011163/1 [EPSRC] Engineering and Physical Sciences Research Council http://dx.doi.org/10.13039/501100000266 UNSPECIFIED International Business Machines Corporation http://dx.doi.org/10.13039/100004316
Conference Paper Type:	Paper
Title of Event:	32nd International Symposium on Distributed Computing (DISC 2018)
Type of Event:	Conference
Location of Event:	New Orleans, LA
Date(s) of Event:	15-19 Oct 2018
Related URLs:	Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads