License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2018.16
URN: urn:nbn:de:0030-drops-98057
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9805/
Go to the corresponding LIPIcs Volume Portal

Czumaj, Artur ; Konrad, Christian

Detecting Cliques in CONGEST Networks

pdf-format:
LIPIcs-DISC-2018-16.pdf (0.6 MB)

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_l 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_l requires Omega(sqrt{n} / b) communication rounds, for every 4 <=l <=sqrt{n}, and Omega(n / (l b)) rounds for every l >= sqrt{n}, 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.

BibTeX - Entry

@InProceedings{czumaj_et_al:LIPIcs:2018:9805,
  author =	{Artur Czumaj and Christian Konrad},
  title =	{{Detecting Cliques in CONGEST Networks}},
  booktitle =	{32nd International Symposium on Distributed Computing  (DISC 2018)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Ulrich Schmid and Josef Widder},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9805},
  URN =		{urn:nbn:de:0030-drops-98057},
  doi =		{10.4230/LIPIcs.DISC.2018.16},
  annote =	{Keywords: Lower bounds, CONGEST, subgraph detection, two-party communication}
}

Keywords: Lower bounds, CONGEST, subgraph detection, two-party communication
Collection: 32nd International Symposium on Distributed Computing (DISC 2018)
Issue Date: 2018
Date of publication: 04.10.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI