Prüfen, ob in gerichteter azyklischer Grafik ein Pfad zwischen zwei Vertices existiert - Abfragen

Question

Diese Frage kann in O (n + m) pro Abfrage leicht gelöst werden, jedoch ist es möglich, solche Anfragen in besserer Komplexität mit besserer Vorverarbeitung als O zu beantworten (n²)?

Im Baum kann es einfach durch die Arbeit mit Vorbestellung und in Reihenfolge durchgeführt werden. Ich habe etwas ähnliches in DAG versucht, aber es macht keinen Sinn.

Ich habe auch versucht, dieses Problem in LCA in DAG Problem zu ändern, aber LCA in DAG finden kann nicht schnell genug gelöst werden. Anzahl der Scheitelpunkte, bis zu 10^5

m - - Anzahl der Kanten, bis zu 10^5

q

n:

---

Um Einschränkungen sagen wir präzise - Anzahl der Abfragen, bis zu 10^5

Answer 1

Interessante Frage. Meine Intuition sagt "Nein". Ich habe es noch nicht durchdacht.

Allerdings (unter der Annahme, dass diese Frage keine theoretische ist), für praktische Zwecke können Sie eine Bloom filter verwenden.

Eine mögliche Lösung für Ihr Problem mit einem Bloom-Filter würde zuerst K verschiedene Ordnungen des Graphen generieren und für jeden die Zuordnung von einem Knoten zu seinem Index in dieser Reihenfolge speichern. Um dann die "Erreichbarkeit" von N1 zu N2 zu testen, überprüfen Sie (für jede Reihenfolge), ob der Index-von-N1 kleiner als der Index-von-N2 ist (diese Überprüfung ist O (1)). Wenn dies für alle Aufträge gilt, ist es mit ziemlich guter Wahrscheinlichkeit erreichbar (assuming K is big enough). (Abhängig von Ihrem Anwendungsfall in der realen Welt kann es sogar in Ordnung sein, solche Fehlalarme gelegentlich zu korrigieren, oder Sie können dann die zuverlässige O (N + M) Prüfung durchführen). Sonst ist es definitiv nicht.

Answer 2

Ich habe das Gefühl, dass es eine Lösung in den folgenden Zeilen geben könnte, aber das ist keineswegs eine vollständige Lösung.

Sei S eine Teilmenge von Vertices. Für jeden Vertex V im Graph betrachte man die Menge D_S (V), die ich wie folgt definiere: D_S (V) = {V} wenn V in S, und ansonsten ist D_S (V) die Vereinigung von {V} mit die Mengen D_S (W) für alle direkten Nachkommen W von V. (Das heißt, es sind "alle möglichen Nachkommen von V, aber höre die Rekursion auf, wenn du ein Element von V triffst.") Die Frage ist: Können wir eine Menge finden? S so, dass die Größe von S O (f (N)) ist und auch D_S (V) die Größe O (g (N)) für alle V hat, und wobei f und g asymptotisch sublinear sind? (Vielleicht können wir zum Beispiel sqrt für beide erreichen.)

Wenn wir das finden können, schlage ich die folgende Strategie vor. Für die Vorverarbeitung erstellen Sie für jedes U in S eine Hash-Tabelle, die alle Knoten enthält, die schließlich von U erreichbar sind. Dies kann in O (f (N) * M) erreicht werden; das ist nicht unbedingt besser als O (N^2), aber mindestens besser als O (M * Q).

Jetzt, um eine Abfrage zu beantworten "ist U erreichbar von V?", Das ist trivial wenn V in S. Andernfalls überprüfen wir, ob V = U, in diesem Fall ist es auch trivial. Schließlich wenden wir den gleichen Prozess rekursiv auf alle Nachkommen von V an und geben "ja" zurück, wenn die Antwort in beiden Fällen "ja" ist, aber "nein" nur, wenn wir niemals U finden. Diese Rekursion dauert bis O (g (N)) Schritte.

Die Frage, die bleibt, ist, wie man S auswählt. Ich denke, wenn der Graph aus einem Prozess entsteht, in dem der Out-Grad einem Potenzgesetz folgt, könnte man einfach die sqrt (N) Eckpunkte mit den höchsten Out-Grades nehmen.Aber zum Beispiel, wenn wir den Graphen auf N = 2 * K Ecken (i, 0) und (i, 1) haben, mit K^2 Kanten: von jedem (i, 0) zu jedem (j, 1); dann gibt es keine geeignete Teilmenge S. Aber vielleicht haben Graphen, die kein geeignetes S haben, notwendigerweise einen Grad an Einheitlichkeit, den wir ausnutzen können ... oder vielleicht auch nicht. Ich weiß es nicht. Irgendwelche Ideen, lass es mich wissen!