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.2017.10
URN: urn:nbn:de:0030-drops-79969
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7996/
Go to the corresponding LIPIcs Volume Portal

Censor-Hillel, Keren ; Khoury, Seri ; Paz, Ami

Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model

pdf-format:
LIPIcs-DISC-2017-10.pdf (0.6 MB)

Abstract

We present the first super-linear lower bounds for natural graph problems in the CONGEST model, answering a long-standing open question.

Specifically, we show that any exact computation of a minimum vertex cover or a maximum independent set requires a near-quadratic number of rounds in the CONGEST model, as well as any algorithm for computing the chromatic number of the graph. We further show that such strong lower bounds are not limited to NP-hard problems, by showing two simple graph problems in P which require a quadratic and near-quadratic number of rounds.

Finally, we address the problem of computing an exact solution to weighted all-pairs-shortest-paths (APSP), which arguably may be considered as a candidate for having a super-linear lower bound. We show a simple linear lower bound for this problem, which implies a separation between the weighted and unweighted cases, since the latter is known to have a sub-linear complexity. We also formally prove that the standard Alice-Bob framework is incapable of providing a super-linear lower bound for exact weighted APSP, whose complexity remains an intriguing open question.

BibTeX - Entry

@InProceedings{censorhillel_et_al:LIPIcs:2017:7996,
  author =	{Keren Censor-Hillel and Seri Khoury and Ami Paz},
  title =	{{Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Andr{\'e}a W. Richa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7996},
  URN =		{urn:nbn:de:0030-drops-79969},
  doi =		{10.4230/LIPIcs.DISC.2017.10},
  annote =	{Keywords: CONGEST, Lower Bounds, Minimum Vertex Cover, Chromatic Number, Weighted APSP}
}

Keywords: CONGEST, Lower Bounds, Minimum Vertex Cover, Chromatic Number, Weighted APSP
Collection: 31st International Symposium on Distributed Computing (DISC 2017)
Issue Date: 2017
Date of publication: 12.10.2017

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