2026-08-16T05:33:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7996 2024-03-06T10:41:38Z ddc:004 open_access

Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model Censor-Hillel, Keren Khoury, Seri Paz, Ami CONGEST Lower Bounds Minimum Vertex Cover Chromatic Number Weighted APSP 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Keren Censor-Hillel and Seri Khoury and Ami Paz 2017 Is Part Of LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2017.10 urn:nbn:de:0030-drops-79969 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.10 eng https://creativecommons.org/licenses/by/3.0/legalcode