Vi presenterar de första superlinjära nedre gränserna för naturliga grafproblem i CON-GEST-modellen och svarar på en långvarig öppen fråga. Specifikt visar vi att varje exakt beräkning av en minimal vertex cover eller en maximal oberoende uppsättning kräver  på 2 / log 2 n) rundor i det värsta fallet i CONGEST modellen, samt någon algoritm för χ-färgning en graf, där χ är det kromatiska antalet av grafen. Vi visar vidare att sådana starka nedre gränser inte är begränsade till NP-hårda problem, genom att visa två enkla grafproblem i P som kräver ett kvadratiskt och närbildande antal rundor. Slutligen tar vi upp problemet med att beräkna en exakt lösning på viktade alla-parkortaste-sökvägar (APSP), som utan tvekan kan betraktas som en kandidat för att ha en super-linjär lägre gräns. Vi visar en enkel (n) lägre gräns för detta problem, vilket innebär en åtskillnad mellan de viktade och oviktade fallen, eftersom de senare är kända för att ha en komplexitet av (n/ log n). Vi bevisar också formellt att Alice-Bobs standardramverk inte är i stånd att tillhandahålla en superlinjär lägre gräns för exakt viktad APSP, vars komplexitet fortfarande är en spännande öppen fråga.
I REF visar det sig att det i CONGEST-modellen både krävs tid (n 2) för att beräkna optimala lösningar till maximal oberoende uppsättning och minsta vertex-täckesproblem.
Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}