Wie lange dauert es, einen kurzen Zyklus in einem zufälligen Diagramm zu finden?

Sei ein zufälliger Graph an Kanten. Mit sehr hoher Wahrscheinlichkeit hat viele Zyklen. Unser Ziel ist es, einen dieser Zyklen so schnell wie möglich auszugeben . $G \sim G(n, n^{-1/2})$ $\approx n^{3/2}$ $G$ $4$ $4$

Angenommen, wir haben Zugriff auf in Form einer Adjazenzliste, können wir mit konstanter Wahrscheinlichkeit in Zeit wie folgt erfolgreich sein: Wählen Sie einen beliebigen Knoten und beginnen Sie mit der Erzeugung zufälliger Pfade ab ; Sobald wir zwei unterschiedliche Pfade gefunden haben, die sich einen Endpunkt teilen, sind wir fertig. Es gibt mögliche Endpunkte, und nach dem Geburtstagsparadoxon werden wir mit konstanter Wahrscheinlichkeit Erfolg haben, nachdem wir ungefähr von ihnen entdeckt haben. $G$ $O(\sqrt{n})$ $v$ $2$ $v$ $2$ $n$ $\sqrt{n}$

Können wir es besser machen? Ist insbesondere ein Algorithmus mit konstanter Zeit möglich, der mit konstanter Wahrscheinlichkeit erfolgreich ist?

graph-theory graph-algorithms property-testing random-graphs GMB
quelle

Mir scheint, dieses Diagramm hat zu wenige Kanten, um die gewünschte Eigenschaft zu haben. Wenn Sie die Standardterminologie verwenden, ähnelt es einem -Beispiel mit

G (n, p)

$G(n,p)$

p = (\sqrt{n} / C (n, 2)) = O (n^{- 3 / 2})

$p=(\sqrt{n}/C(n,2))=O(n^{-3/2})$

Kodlu

Danke, du hast Recht, dass ich (bearbeitet) gemeint habe . Diese Graphen haben jedes Mal wenn zwei Knoten sich Nachbarn teilen , was mit konstanter Wahrscheinlichkeit pro Knotenpaar geschieht.

p = n^{- 1 / 2}

$p = n^{-1/2}$

C_{4}

$C_4$

\geq 2

$\ge 2$

GMB

Ich verwende hier die Terminologie ( en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model ), wobei jede Kante unabhängig mit der Wahrscheinlichkeit

- also Kanten in Erwartung.

p

$p$

p \cdot (\binom{n}{2})

$p \cdot {n \choose 2}$

GMB

Antworten:

Nein, Sie können Abfragen nicht beantworten. Ich werde erklären, wie man die Beweisskizze von exfret auf eine Weise formalisiert , die für adaptive Algorithmen funktioniert. Dies alles wird in der Antwort von Exfret erwartet; Ich fülle nur einige Details aus. $\Theta(\sqrt{n})$

Betrachten Sie einen (möglicherweise adaptiven) Algorithmus, der eine Folge von Abfragen ausgibt, wobei jede Abfrage entweder "die te Kante der Adjazenzliste des Scheitelpunkts abrufen" oder "testen, ob die Scheitelpunkte durch eine Kante verbunden sind". Wir können davon ausgehen, dass keine Abfrage wiederholt wird, da jeder Algorithmus, der eine Abfrage wiederholt, in einen Algorithmus umgewandelt werden kann, der keine Abfrage wiederholt. In ähnlicher Weise können wir annehmen, dass der Algorithmus niemals eine Konnektivitätsabfrage für ein Paar von Scheitelpunkten durchführt, von denen bereits bekannt ist, dass sie durch eine Kante verbunden sind (nämlich das Testen von wenn zuvor von einer Abrufabfrage für , oder war zuvor von einer Abrufabfrage auf $i$ $v$ $v,w$ $v,w$ $w$ $v$ $v$ $w$ , oder wir haben zuvor die Konnektivität von ) getestet . $w,v$

Lassen das Ereignis bezeichnen , daß während der ersten - Abfragen, keine Vertex von mehr zurückgeführt wird als eine Fetch-Abfrage, und keine fetch-Abfrage gibt eine Vertex , die zuvor abgefragt wurden, und dass kein Konnektivitätstest-query returns „verbunden ". Wir werden beweisen, dass wenn . Daraus folgt, dass kein Algorithmus, der Abfragen durchführt, eine konstante Wahrscheinlichkeit haben kann, einen 4-Zyklus zu finden. $E_k$ $k$ $w$ $\Pr[E_q] = 1-o(1)$ $q=o(\sqrt{n})$ $o(\sqrt{n})$

Wie beweisen wir das? Berechnen wir . Es gibt zwei Fälle: Entweder ist die te Abfrage eine Abrufabfrage oder eine Konnektivitätstestabfrage: $\Pr[E_k|E_{k-1}]$ $k$

Wenn die te Abfrage eine Abrufabfrage für den Scheitelpunkt , werden Scheitelpunkte unter den ersten Abfragen erwähnt, und wenn die te Abfrage eine davon , haben wir andernfalls wir werden . Jetzt ist die Antwort auf die te Abfrage gleichmäßig auf eine Menge von Scheitelpunkten verteilt, wobei alle Scheitelpunkte enthält, die nicht durch vorherige Abrufabfragen auf , sodass die Antwort auf die te Abfrage gleichmäßig auf eine Menge verteilt ist mit einer Größe von mindestens $k$ $v$ $2(k-1)$ $k-1$ $k$ $\neg E_k$ $E_k$ $k$ $S$ $S$ $v$ $k$ $n-k+1$ . Die Wahrscheinlichkeit, mindestens eine davon zu treffen, ist , also in diesem Fall . $\le 2(k-1)/(n-k+1)$ $\Pr[E_k|E_{k-1}] \ge 1 - 2(k-1)/(n-k+1)$
Wenn die te Abfrage eine Konnektivitätstestabfrage ist, dann . $k$ $\Pr[E_k|E_{k-1}] \ge 1 - 1/\sqrt{n}$

In beiden Fällen haben wir , wenn $q=o(\sqrt{n})$

Pr [E_{k} | E_{k - 1}] \geq 1 - \frac{2 (k - 1)}{(n - k + 1)} .

$\Pr[E_k|E_{k-1}] \ge 1 - {2(k-1) \over (n-k+1)}.$

Jetzt,

Pr [E_{q}] = \prod_{k = 1}^{q} Pr [E_{k} | E_{q - 1}] .

$\Pr[E_q] = \prod_{k=1}^q \Pr[E_k|E_{q-1}].$

Wenn , dann $k \le q \le \sqrt{n}$

Pr [E_{k} | E_{k - 1}] \geq 1 - \frac{2 q}{n - q},

$\Pr[E_k|E_{k-1}] \ge 1 - {2q \over n - q},$

Pr [E_{q}] \geq (1 - \frac{2 q}{n - q})^{q} .

$\Pr[E_q] \ge (1 - {2 q \over n - q})^q.$

Die rechte Seite ist ungefähr . Wenn , ist dies . $\exp \{ - 2q^2/(n-q)\}$ $q = o(\sqrt{n})$ $1 -o(1)$

Zusammenfassend: wenn . Daraus folgt, dass Sie benötigen, um eine konstante Wahrscheinlichkeit zu haben, einen Zyklus zu finden (geschweige denn einen 4-Zyklus). $\Pr[E_q] = 1-o(1)$ $q=o(\sqrt{n})$ $\Omega(\sqrt{n})$

DW
quelle

"Wenn die k-te Abfrage eine Konnektivitätstestabfrage ist, ist ." Ich denke ? (Auch wenn ja, die Schlussfolgerung geht natürlich immer noch durch.)

P r [E k | E k - 1] \geq 1 - 1 / n

$Pr[Ek|Ek−1]≥1−1/n$

1 - 1 / \sqrt{n}

$1-1/\sqrt{n}$

usul

@usul, oops, ja, danke! Fest.

Nehmen wir an, wir können nur die te Kante der Adjazenzliste eines bestimmten Scheitelpunkts abfragen (von der ich annehme, dass sie nicht sortiert ist) oder ob zwei gegebene Scheitelpunkte benachbart sind. In diesem Fall sollten Abfragen erforderlich sein, um überhaupt einen Zyklus zu finden. Dies liegt daran, dass die Wahrscheinlichkeit dass alle unsere Abfragen des ersten Typs unterschiedliche Scheitelpunkte zurückgeben und dass alle unsere Abfragen des zweiten Typs zurückgeben, dass die beiden Scheitelpunkte nicht verbunden sind. $i$ $\sqrt n$ $1-o(1)$

Bitte korrigieren Sie mich, wenn ich irgendwo falsch liege oder das Problem falsch verstehe.

exfret
quelle

Diese Proofskizze klingt für mich so, als ob sie nur für nicht adaptive Algorithmen funktioniert (dh Abfragen, die im Voraus behoben wurden).

Usul

@usul Warum sollte das so sein? Whp wir verwenden sowieso nur einen Zweig des Entscheidungsbaums.

Exfret

Vielleicht sollte ich das klarstellen. Es sollte klar sein, dass wir keinen 4-Zyklus mit konstanter Wahrscheinlichkeit ausgeben können, wenn wir wie vorgeschrieben Antworten auf unsere Fragen erhalten. Für jeden Entscheidungsbaum der Tiefe besteht jedoch eine Chance, dass wir über einen solchen Zweig gesendet werden.

o (\sqrt{n})

$o(\sqrt n)$

1 - o (1)

$1-o(1)$

Exfret

Vielen Dank! Ich habe (etwas willkürlich) die andere ausgearbeitete Version akzeptiert, aber es scheint, als hättest du sie verstanden. Schätzen Sie die Antwort.

GMB

@ GMB Ich denke, Sie haben die richtige Entscheidung getroffen. Die andere ist eine Antwort von viel höherer Qualität und verdient es, zuerst von anderen gesehen zu werden.

Exfret