Untere Grenzen der Laufzeit von Graph-Algorithmen

8

Gibt es nicht triviale Untergrenzen für die Laufzeit von Graph-Algorithmen in RAM / PRAM / Berechnungsmodellen? Ich suche hier nicht nach den NP-Härteergebnissen.

Folgendes ist ein Ergebnis, das ich finden konnte [siehe Lit. L92]:

  • Das 3-Färben eines n-Zyklus erfordert Zeit.Ω(Log∗⁡n)

Ich war neugierig zu wissen, ob es Fortschritte / Arbeiten in Richtung der Erzielung von Untergrenzen für Probleme wie: Kürzeste Pfade (mit / ohne negative Gewichte), Mincut, st Maximum Flows, Maximum (Kardinalität / gewichtet) Matching gegeben hat. Alle diesbezüglichen Referenzen werden sehr geschätzt und sind hilfreich.

Referenz

[ L92 ] N. Linial, Lokalität in Algorithmen für verteilte Graphen, SIAM Journal on Computing, 1992, 21 (1), S. 193-201

EDIT: Wie von Robin Kothari in den Kommentaren vorgeschlagen, mache ich die Frage gezielter.

cc.complexity-theory reference-request graph-algorithms lower-bounds Rizwanhudda
quelle
5
Ohne das Modell einzuschränken, könnte eine angemessene Antwort auf diese Frage für Seiten erfolgen. Neben der Beschränkung auf Grafikprobleme lautet diese Frage im Wesentlichen: "Welche Untergrenzen sind in CS bekannt?" Und die Beschränkung auf Grafikprobleme ist nicht stark, da wir in Modellen, in denen wir für ein Problem gute Untergrenzen (z. B. Streaming, Entscheidungsbäume, Kommunikationskomplexität) nachweisen können, auch für Grafikprobleme gute Untergrenzen nachweisen können.
Robin Kothari
@RobinKothari Ich habe die Frage jetzt bearbeitet. Ich suche nach Untergrenzen in PRAM / RAM-Modellen. Schlagen Sie weitere Änderungen vor?
Rizwanhudda

Antworten:

3

Im PRAM-Modell ohne Bitoperationen sind ziemlich starke Untergrenzen bekannt. Zum Beispiel kann man in diesem Modell den Min-Cut in nicht lösenÖ(n)2Ö(n)

Obwohl es sich um ein eingeschränktes Modell handelt, ist es stark genug, um die Determinante effizient zu berechnen, und enthält die meisten Standardalgorithmen für kombinatorische Optimierungsprobleme mit mehreren Zeitpunkten. Weitere Informationen finden Sie hier , hier oder im Originalpapier.

[1] Mulmuley, K. Untergrenzen in einem parallelen Modell ohne Bitoperationen . SIAM J. Comput., 28 (4), 1460–1509, 1999. ( von der Webseite des Autors ohne Paywall )

Joshua Grochow
quelle