Trouver un ensemble indépendant maximal en parallèle

Sur un graphique $G(V,E)$, nous effectuons le processus suivant:

• Initialement, tous les nœuds $V$ sont incolores.
• Bien qu'il existe des nœuds non colorés dans $V$, chaque nœud non coloré effectue les opérations suivantes:
  • Sélectionne un nombre réel aléatoire et l'envoie à tous ses voisins;
  • Compare son nombre au nombre de ses voisins; si son propre nombre est strictement le plus petit, alors le voisin se peint en rouge et avertit tous ses voisins.
  • Si un voisin est devenu rouge, ce nœud se peint en noir.

Par exemple:

• Supposons que le graphique soit un chemin: abcde.
• Supposons que les chiffres de la première étape soient: 1-2-0-3-4.
• Les nœuds a et c sont peints en rouge; les nœuds b et d sont peints en noir.
• Dans la deuxième étape, seul le nœud e reste incolore; il est trivialement minimal donc il se peint en rouge.

MA QUESTION EST: quel est le nombre moyen d'étapes que ce processus prend avant que tous les nœuds soient colorés?

Mon calcul actuel me conduit à un $O(1)$estimation, ce qui semble trop beau pour être vrai. Voici le calcul:

Considérons un nœud $v$ avec $d$voisins. La probabilité que$v$ sera le plus petit parmi ses voisins est $1/(d+1)$. Si cela se produit, alors$v$et tous ses voisins seront colorés. Ainsi, le nombre attendu de sommets colorés à chaque étape est$(d+1)/(d+1)=1$ par nœud . Par conséquent, le nombre total attendu de sommets colorés à chaque étape est$O(n)$, donc dans $O(1)$ tous les nœuds seront colorés.

Si cette analyse est erronée (ce qui est probablement le cas), alors quel est le nombre réel d'étapes?

EDIT: Comme indiqué par @JukkaSuomela, l'algorithme décrit ci-dessus est dû à Metivier et al, 2011 et est expliqué et analysé dans ces notes de cours . Ils prouvent que le temps d'exécution est$O(\log n)$.

Mais je ne suis toujours pas convaincu que cette analyse soit rigoureuse. Dans tous les graphiques que j'ai vérifiés, il semble que l'algorithme se termine en$O(1)$ heure prévue.

Ma question est maintenant: quel est le pire des graphiques dans lequel cet algorithme nécessite en effet $O(\log n)$ pas en moyenne?

Il y a une erreur mineure, la probabilité de $v$ être minimal est $1/(d+1)$. Cela ne change rien, mais cela vaut quand même la peine d'être souligné.

Le problème est que les événements que vous résumez ne sont pas disjoints. Considérez deux sommets qui ne sont pas adjacents mais qui ont un voisin commun. Si les deux sommets finissent par être minimes parmi leurs voisins, alors le voisin commun est compté comme étant coloré deux fois.

Nous devons examiner de plus près ce qui se passe dans un sommet. Calculons la probabilité (et donc l'attente du variabele indicateur) qu'un seul sommet se colore.

Supposons, pour les besoins de l'analyse, que le graphique est $d$-régulier et ne contient ni triangles ni carrés. Nous calculerons la chance qu'un sommet donné$v$ne pas se couleur. Il y a$d+1$ possibilités: le $v$ pourrait être le plus petit parmi ses voisins, $v$ pourrait être le deuxième plus petit, le troisième plus petit, et ainsi de suite ... Nous ne sommes pas intéressés par le cas où il est le plus petit, car alors il se colore.

Si $v$est le deuxième plus petit, il y a un sommet qui est plus petit. La probabilité que ce sommet soit le plus petit parmi ses voisins est$\frac{1}{d}$ (Et ainsi $v$se colorer). La probabilité que les voisins restants soient les plus petits parmi leurs voisins est de 0 (puisque$v$est plus petit). La probabilité totale (de$v$ ne se colorent pas) de ce cas est$\frac{1}{d+1}\cdot\frac{d-1}{d}$.

Si $v$est le troisième plus petit, il y a deux sommets plus petits. La probabilité de ce cas est$\frac{1}{d+1}\cdot(\frac{d-1}{d})^2$.

En continuant comme ça, nous constatons que la probabilité que $v$ne pas obtenir est de couleur$\frac{1}{d+1}\Sigma_{i=1}^d (\frac{d-1}{d})^i$. La probabilité qu'un sommet donné se colore est donc$1-\frac{1}{d+1}\Sigma_{i=1}^d (\frac{d-1}{d})^i$. Comme$d\to \infty$, la probabilité devient $\frac{1}{e}\approx 0.368$.

Par conséquent, la probabilité qu'un sommet donné se colore est une constante, donc le nombre attendu de sommets qui se colorent à la première étape est en effet $O(n)$.

Cela ne fait pas l'algorithme $O(1)$. En supposant que la probabilité reste constante (ce qui n'est pas entièrement justifié étant donné que les nœuds se colorent et ne participent plus à l'algorithme, le graphique ne reste pas$d$-régulier), dans le $k$-tape il y aura (en attente) ${(\frac{1}{e})}^kn$nœuds incolores. La décroissance est exponentielle, donc l'algorithme prend$O(\log n)$ pas.

Peut-être que quelqu'un d'autre pourra offrir une analyse plus précise, mais d'après mon argumentation, il semble probable que l'algorithme soit $O(\log n)$.