A Study of Random Walk Based Algorithms for Efficient Generation of Uniform Spanning Trees

Árvore geradora uniforme é a medida de probabilidade uniforme no conjunto de árvores de geradoras de um grafo. Exploradas desde o consagrado trabalho de Kirchhoff na década de 1840, essas árvores aleatórias estão entre os objetos aleatórios mais antigos e mais amplamente estudados na teoria dos grafos e estão relacionados a diversos temas importantes em probabilidade discreta, além de encontrarem aplicação em muitas áreas. Não é de surpreender que a tarefa de gerar eficientemente árvores geradoras uniformes tenha recebido muita atenção. No entanto, nas últimas décadas, as estratégias mais promissoras para o problema mudaram significativamente. Esse avanço ocorreu com os algoritmos de Aldous-Broder e Wilson, que constroem árvores utilizando passeios aleatórios. Neste trabalho, estudamos o comportamento transiente destes dois algoritmos. Introduzimos a noção de branches, que são caminhos adicionadas às árvores em determinados tempos de parada. Essa interpretação é usada para mostrar uma equivalência transiente entre os dois algoritmos em grafos completos. A equivalência leva a uma abordagem híbrida que gera árvores geradoras uniformes de grafos completos mais rapidamente do que cada um dos dois algoritmos. Propomos uma metodologia para explorar essa abordagem híbrida em um cenário mais geral, mostrando a viabilidade em alguns exemplos. Por fim, mostramos como a metodologia pode ser adaptada para gerar árvores aleatórias com probabilidade proporcional ao número de uma dada subárvore fornecida como parâmetro.