Parallel dazu eine maximale unabhängige Menge finden

In einem Graphen wir den folgenden Prozess aus:$G(V,E)$

• Anfangs sind alle Knoten in ungefärbt.$V$
• Während es in ungefärbte Knoten gibt, führt jeder ungefärbte Knoten Folgendes aus: $V$
  • Wählt eine zufällige reelle Zahl aus und sendet sie an alle Nachbarn.
  • Vergleicht seine Nummer mit der Anzahl seiner Nachbarn; Wenn seine eigene Zahl streng klein ist, malt sich der Nachbar rot und benachrichtigt alle seine Nachbarn.
  • Wenn ein Nachbar rot wurde, malt sich dieser Knoten schwarz.

Zum Beispiel:

• Angenommen, der Graph ist ein Pfad: abcde.
• Angenommen, die Zahlen im ersten Schritt sind: 1-2-0-3-4.
• Die Knoten a und c sind rot gestrichen. Knoten b und d sind schwarz lackiert.
• Im zweiten Schritt bleibt nur der Knoten e ungefärbt; es ist trivial minimal, also malt es sich rot.

Meine Frage ist: Wie viele Schritte dauert dieser Prozess durchschnittlich, bevor alle Knoten gefärbt sind?

Meine aktuelle Berechnung führt mich zu einer -Schätzung, die zu gut scheint, um wahr zu sein. Hier ist die Berechnung:$O(1)$

Betrachten Sie einen Knoten mit d Nachbarn. Die Wahrscheinlichkeit, dass v unter seinen Nachbarn am kleinsten ist, beträgt 1 / ( d + 1 ) . In diesem Fall werden v und alle seine Nachbarn farbig dargestellt. Die erwartete Anzahl von Eckpunkten, die in jedem Schritt gefärbt werden, beträgt also ( d + 1 ) / ( d + 1 ) = 1 pro Knoten . Daher ist die erwartete Gesamtzahl der in jedem Schritt gefärbten Eckpunkte O ( n ) , also in O ( $v$$d$$v$$1/(d+1)$$v$$(d+1)/(d+1)=1$ $O(n)$ Mal werden alle Knoten gefärbt.$O(1)$

Wenn diese Analyse falsch ist (was wahrscheinlich der Fall ist), wie viele Schritte gibt es dann tatsächlich?

BEARBEITEN: Wie von @JukkaSuomela festgestellt, stammt der oben beschriebene Algorithmus von Metivier et al., 2011 und wird in diesen Vorlesungsunterlagen erläutert und analysiert . Sie beweisen, dass die Laufzeit .$O(\log n)$

Ich bin jedoch immer noch nicht davon überzeugt, dass diese Analyse eng ist. In allen von mir überprüften Diagrammen scheint der Algorithmus in der erwarteten -Zeit abgeschlossen zu sein.$O(1)$

Meine Frage ist nun: Was ist ein Worst-Case-Graph, in dem dieser Algorithmus tatsächlich durchschnittlich Schritte erfordert ?$O(\log n)$

$v$$1/(d+1)$

Das Problem ist, dass die Ereignisse, die Sie summieren, nicht disjunkt sind. Betrachten Sie zwei Eckpunkte, die nicht benachbart sind, aber einen gemeinsamen Nachbarn haben. Wenn beide Eckpunkte unter ihren Nachbarn minimal sind, wird der gemeinsame Nachbar als zweimal gefärbt gezählt.

Wir müssen genauer untersuchen, was in einem Scheitelpunkt passiert. Berechnen wir die Wahrscheinlichkeit (und damit die Erwartung der Indikatorvariablen), dass ein einzelner Scheitelpunkt gefärbt wird.

$d$$v$$d+1$$v$$v$

$v$$\frac{1}{d}$$v$$v$$v$ $\frac{1}{d+1}\cdot\frac{d-1}{d}$

$v$$\frac{1}{d+1}\cdot(\frac{d-1}{d})^2$

$v$$\frac{1}{d+1}\Sigma_{i=1}^d (\frac{d-1}{d})^i$$1-\frac{1}{d+1}\Sigma_{i=1}^d (\frac{d-1}{d})^i$$d\to \infty$$\frac{1}{e}\approx 0.368$

$O(n)$

$O(1)$$d$$k$${(\frac{1}{e})}^kn$$O(\log n)$

$O(\log n)$