Encontrando um conjunto independente máximo em paralelo

Em um gráfico $G(V,E)$, fazemos o seguinte processo:

• Inicialmente, todos os nós em $V$ são incolores.
• Embora existam nós não coloridos em $V$, cada nó não colorido faz o seguinte:
  • Seleciona um número real aleatório e o envia a todos os seus vizinhos;
  • Compara seu número com o número de seus vizinhos; se o seu número é estritamente menor, o vizinho pinta-se de vermelho e notifica todos os vizinhos.
  • Se um vizinho ficar vermelho, esse nó se pintará de preto.

Por exemplo:

• Suponha que o gráfico seja um caminho: abcde.
• Suponha que os números na primeira etapa sejam: 1-2-0-3-4.
• Os nós a e c são pintados de vermelho; os nós ed são pintados de preto.
• Na segunda etapa, apenas o nó e permanece sem cor; é trivialmente mínimo, portanto se pinta de vermelho.

MINHA PERGUNTA É: qual é o número médio de etapas que esse processo executa antes de todos os nós serem coloridos?

Meu cálculo atual me leva a uma $O(1)$estimativa, o que parece bom demais para ser verdade. Aqui está o cálculo:

Considere um nó $v$ com $d$vizinhos. A probabilidade de que$v$ será o menor entre seus vizinhos é $1/(d+1)$. Se isso acontecer, então$v$e todos os seus vizinhos serão coloridos. Portanto, o número esperado de vértices coloridos em cada etapa é$(d+1)/(d+1)=1$ por nó . Portanto, o número total esperado de vértices coloridos em cada etapa é$O(n)$então em $O(1)$ tempo em que todos os nós serão coloridos.

Se essa análise estiver errada (o que provavelmente é o caso), qual é o número real de etapas?

EDIT: Como observado por @JukkaSuomela, o algoritmo descrito acima é devido a Metivier et al, 2011 e é explicado e analisado nestas notas de aula . Eles provam que o tempo de execução é$O(\log n)$.

Mas ainda não estou convencido de que essa análise seja rigorosa. Em todos os gráficos que verifiquei, parece que o algoritmo termina em$O(1)$ tempo esperado.

Minha pergunta é agora: qual é o pior gráfico em que esse algoritmo realmente exige $O(\log n)$ passos em média?

Há um pequeno erro, a probabilidade de $v$ ser mínimo é $1/(d+1)$. Isso não muda nada, mas ainda vale a pena destacar.

O problema é que os eventos que você está somando não são disjuntos. Considere dois vértices que não são adjacentes, mas têm um vizinho em comum. Se ambos os vértices acabam sendo mínimos entre os vizinhos, o vizinho comum é contado como colorido duas vezes.

Precisamos examinar o que acontece em um vértice mais de perto. Vamos calcular a probabilidade (e, portanto, a expectativa da variável indicador) de um único vértice ficar colorido.

Suponha, para fins de análise, que o gráfico é $d$-regular e não contém triângulos ou quadrados. Vamos calcular a chance de um determinado vértice$v$se não ficar colorido. tem$d+1$ possibilidades: o $v$ pode ser o menor entre os vizinhos, $v$ pode ser o segundo menor, o terceiro menor e assim por diante ... Não estamos interessados ​​no caso de ser o menor, desde então fica colorido.

E se $v$é o segundo menor, existe um vértice menor. A probabilidade desse vértice ser menor entre seus vizinhos é$\frac{1}{d}$ (e assim $v$ficando colorido). A probabilidade de os vizinhos restantes serem menores entre os vizinhos é 0 (desde$v$é menor). A probabilidade total (de$v$ não ficar colorido) neste gabinete é$\frac{1}{d+1}\cdot\frac{d-1}{d}$.

E se $v$é o terceiro menor, existem dois vértices menores. A probabilidade deste caso é$\frac{1}{d+1}\cdot(\frac{d-1}{d})^2$.

Continuando assim, descobrimos que a probabilidade de que $v$se não conseguir é colorido$\frac{1}{d+1}\Sigma_{i=1}^d (\frac{d-1}{d})^i$. A probabilidade de um determinado vértice ficar colorido é, portanto,$1-\frac{1}{d+1}\Sigma_{i=1}^d (\frac{d-1}{d})^i$. Como$d\to \infty$, a probabilidade se torna $\frac{1}{e}\approx 0.368$.

Portanto, a probabilidade de um determinado vértice ficar colorido é uma constante; portanto, o número esperado de vértices coloridos no primeiro passo é realmente $O(n)$.

Isso não torna o algoritmo $O(1)$. Supondo que a probabilidade permaneça constante (o que não é totalmente justificado, considerando que os nós ficam coloridos e não participam mais do algoritmo, o gráfico não permanece$d$-regular), no $k$-ésimo passo: haverá (na expectativa) ${(\frac{1}{e})}^kn$nós não coloridos. A decadência é exponencial, então o algoritmo leva$O(\log n)$ passos.

Talvez alguém mais possa oferecer uma análise mais precisa, mas, pela minha argumentação, parece provável que o algoritmo seja $O(\log n)$.