Encontrar un conjunto independiente máximo en paralelo

En un gráfico , hacemos el siguiente proceso:$G(V,E)$

• Inicialmente, todos los nodos en son incoloros.$V$
• Si bien hay nodos sin color en , cada nodo sin color hace lo siguiente: $V$
  • Selecciona un número real aleatorio y lo envía a todos sus vecinos;
  • Compara su número con el número de sus vecinos; Si su propio número es estrictamente más pequeño, el vecino se pinta de rojo y notifica a todos sus vecinos.
  • Si un vecino se volvió rojo, entonces este nodo se pinta de negro.

Por ejemplo:

• Supongamos que el gráfico es una ruta: abcde.
• Supongamos que los números en el primer paso son: 1-2-0-3-4.
• Los nodos a y c están pintados de rojo; los nodos byd están pintados de negro.
• En el segundo paso, solo el nodo e permanece sin color; es trivialmente mínimo, por lo que se pinta de rojo.

MI PREGUNTA ES: ¿cuál es el número promedio de pasos que toma este proceso antes de que se coloreen todos los nodos?

Mi cálculo actual me lleva a una estimación de , que parece demasiado buena para ser verdad. Aquí está el cálculo:$O(1)$

Considere un nodo con vecinos. La probabilidad de que sea ​​el más pequeño entre sus vecinos es . Si esto sucede, entonces y todos sus vecinos serán coloreados. Entonces, el número esperado de vértices coloreados en cada paso es por nodo . Por lo tanto, el número total esperado de vértices coloreados en cada paso es , por lo que en el tiempo todos los nodos serán coloreados.$v$$d$$v$$1/(d+1)$$v$$(d+1)/(d+1)=1$ $O(n)$$O(1)$

Si este análisis es incorrecto (que probablemente sea el caso), ¿cuál es el número real de pasos?

EDITAR: Como señaló @JukkaSuomela, el algoritmo descrito anteriormente se debe a Metivier et al, 2011 y se explica y analiza en estas notas de clase . Prueban que el tiempo de ejecución es .$O(\log n)$

Pero todavía no estoy convencido de que este análisis sea estricto. En todos los gráficos que verifiqué, parece que el algoritmo se completa en tiempo esperado.$O(1)$

Mi pregunta ahora es: ¿cuál es el peor gráfico en el que este algoritmo realmente requiere pasos en promedio?$O(\log n)$

Hay un error menor, la probabilidad de que sea ​​mínima es . Eso no cambia nada, pero aún vale la pena señalarlo.$v$$1/(d+1)$

El problema es que los eventos que estás sumando no son disjuntos. Considere dos vértices que no son adyacentes pero tienen un vecino común. Si ambos vértices terminan siendo mínimos entre sus vecinos, entonces el vecino común se cuenta como coloreado dos veces.

Necesitamos examinar lo que sucede en un vértice más de cerca. Calculemos la probabilidad (y, por lo tanto, la expectativa de la variable variable del indicador) de que un solo vértice se coloree.

Supongamos, por el bien del análisis, que la gráfica es regular y no contiene triángulos ni cuadrados. Vamos a calcular la probabilidad de que un vértice dado qué no conseguir coloreado. Hay posibilidades de : podría ser el más pequeño entre sus vecinos, podría ser el segundo más pequeño, el tercero más pequeño, y así sucesivamente ... No nos interesa el caso de que sea el más pequeño, desde entonces de colores.$d$$v$$d+1$$v$$v$

Si es el segundo más pequeño, hay un vértice que es más pequeño. La probabilidad de que este vértice sea más pequeño entre sus vecinos es (y, por lo tanto, se colorea). La probabilidad de que los vecinos restantes sean más pequeños entre sus vecinos es 0 (ya que es más pequeño). La probabilidad total (de que no se coloree) de este caso es .$v$$\frac{1}{d}$$v$$v$$v$ $\frac{1}{d+1}\cdot\frac{d-1}{d}$

Si es el tercero más pequeño, hay dos vértices más pequeños. La probabilidad de este caso es .$v$$\frac{1}{d+1}\cdot(\frac{d-1}{d})^2$

Continuando de esta manera, nos encontramos con que la probabilidad de que no no obtener coloreado es . La probabilidad de que un vértice dado se coloree es, por lo tanto, . Como , la probabilidad se convierte en .$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$

Por lo tanto, la probabilidad de que un vértice dado se coloree es una constante, por lo que el número esperado de vértices que se colorean en el primer paso es de hecho .$O(n)$

Eso no hace que el algoritmo . Suponiendo que la probabilidad se mantenga constante (lo que no está completamente justificado considerando que los nodos se colorean y ya no participan en el algoritmo, el gráfico no permanece -regular), en el -ésimo paso habrá (en expectativa) nodos sin color. El decaimiento es exponencial, por lo que el algoritmo toma pasos.$O(1)$$d$$k$${(\frac{1}{e})}^kn$$O(\log n)$

Quizás alguien más pueda ofrecer un análisis más preciso, pero desde mi argumentación parece probable que el algoritmo sea .$O(\log n)$