Berechnung eines transitiven Vervollständigungs- / Pfadexistenz-Orakels

9

Es gab einige Fragen ( 1 , 2 , 3 ) zur transitiven Vervollständigung, die mich zum Nachdenken gebracht haben, ob so etwas möglich ist:

Angenommen, wir erhalten einen eingabegerichteten Graphen und möchten Fragen vom Typ " ?" Beantworten , dh fragen, ob bei der transitiven Vervollständigung eines Graphen eine Kante zwischen zwei Eckpunkten existiert . (äquivalent: " in einen Pfad von nach ?").G(u,v)G+GuvG

Angenommen, nach gegebenem Sie die Vorverarbeitung in der Zeit ausführen und müssen dann die Anfragen in der Zeit beantworten .Gf(n,m)g(n,m)

Wenn (dh keine Vorverarbeitung zulässig ist), können Sie eine Anfrage natürlich am besten in der Zeit beantworten . (Führen Sie DFS von nach und geben Sie true zurück, wenn ein Pfad vorhanden ist.)f=0g(n)=Ω(n+m)uv

Ein weiteres triviales Ergebnis ist, dass Sie, wenn , den transitiven Abschluss berechnen und dann Fragen in beantworten können .f=Ω(min{nm,nω})O(1)

Was ist mit etwas in der Mitte? Wenn Sie z. B. f=n2 Vorverarbeitungszeit zulassen, können Sie Anfragen schneller als O(m+n) beantworten ? Vielleicht auf O(n) verbessern ?

Eine andere Variante ist: Angenommen, Sie haben eine Vorverarbeitungszeit von poly(n,m) , aber nur o(n2) Speicherplatz. Können Sie die Vorverarbeitung verwenden, um Anfragen zu beantworten, die effizienter sind als O(n+m) ?

Können wir generell etwas über den f,g Kompromiss sagen , der die Beantwortung solcher Fragen ermöglicht?

Eine etwas ähnliche Kompromissstruktur wird bei GPS-Systemen in Betracht gezogen, bei denen das Halten einer vollständigen Routing-Tabelle aller paarweisen Entfernungen zwischen Standorten nicht möglich ist. Daher wird die Idee von Entfernungsorakeln verwendet, die eine Teiltabelle speichern, aber eine erhebliche Abfragebeschleunigung über die Berechnung der Entfernung des Ganzen ermöglichen Grafik (ergibt normalerweise nur einen ungefähren Abstand zwischen Punkten).

RB
quelle
Die Hamming-Distanz zwischen den beiden Knoten und j, die in t Hops erreicht werden können, könnte eine aussagekräftigere Metrik sein. ijt
Chad Brewbaker

Antworten:

6

Für planare Graphen gibt es Orakel mit kompakter Erreichbarkeit.

Mikkel Thorup: Kompakte Orakel für Erreichbarkeit und ungefähre Entfernungen in planaren Digraphen . J. ACM 51 (6): 993 & ndash; 1024 (2004)

sind aber "schwer" für allgemeine Graphen (auch spärliche Graphen)

Mihai Patrascu: Vereinheitlichung der Landschaft der unteren Grenzen der Zellsonde . SIAM J. Comput. 40 (3): 827 & ndash; 847 (2011)

Trotzdem gibt es einen Algorithmus, der eine nahezu optimale Erreichbarkeitskennzeichnung berechnen kann

Edith Cohen, Eri Halperin, Uri Zwick, Haim Kaplan: Erreichbarkeits- und Entfernungsabfragen über 2-Hop-Etiketten . SIAM J. Comput. 32 (5): 1338 & ndash; 1355 (2003)

Maxim A. Babenko, Andrew V. Goldberg, Anupam Gupta, Viswanath Nagarajan: Algorithmen zur Optimierung von Hub-Labels . ICALP 2013: 69 & ndash; 80

Aufbauend auf der Arbeit von Cohen et al. und andere, es gibt ziemlich viel angewandte Forschung (Datenbankgemeinschaft), siehe z

Ruoming Jin, Guan Wang: Einfaches, schnelles und skalierbares Oracle . PVLDB 6 (14): 1978-1989 (2013)

Yosuke Yano, Takuya Akiba, Yoichi Iwata und Yuichi Yoshida: Schnelle und skalierbare Erreichbarkeitsabfragen in Diagrammen durch beschnittene Beschriftung mit Orientierungspunkten und Pfaden . CIKM 2013: 1601 & ndash; 1606

Christian Sommer
quelle
4

Ich werde Ihre Frage teilweise beantworten: Es scheint einige Gründe zu geben, warum eine solche Konstruktion schwer zu bekommen sein kann.

T(O(m),O(n))+nq(O(m),O(n))T(m,n)=O(n2)q(m,n)=O(n)O(nω)ω=2

GnX,Y,Z,WvGvX,vY,vZ,vW(u,v)G(uX,vY),(uY,vZ),(uZ,vW)T(O(m),O(n))vX,vWv

n2+o(1)

Jungfrau
quelle