Quais são os obstáculos para estender a ?

13

A prova de Omer Reingold que dá um algoritmo para USTCON (Em um U ndirected gráfico com vértices especiais e , eles são Con ACOPLADO?) Usando apenas logspace. A idéia básica é criar um gráfico de expansão a partir do gráfico original e, em seguida, percorrer o gráfico de expansão. O gráfico do expansor é elaborado ao quadrado o gráfico original logaritmicamente várias vezes. No gráfico do expansor, o diâmetro é apenas logarítmico, portanto, uma pesquisa DFS de profundidade logarítmica é suficiente.s tL=SLst

Estender o resultado para implicaria a existência de um algoritmo de espaço de log para o DSTCON - o mesmo, mas para os gráficos D direcionados. (Às vezes, apenas STCON.) Minha pergunta, talvez um pouco suave, é quais são os principais obstáculos para estender a prova de Reingold a isso?L=NL

Parece que deve haver uma espécie de gráfico de "expansor direcionado". Um tipo de construção semelhante, em que você adiciona arestas correspondentes a caminhos direcionados de comprimento médio e, em seguida, alguns correspondentes a longos; e então você pode percorrer o gráfico com profundidade logarítmica, movendo-se por caminhos curtos para chegar a um longo; depois volte para caminhos curtos no final.

Existe uma falha importante nesse conceito? Ou será que não existem boas construções desses expansores? Ou, de alguma forma, requer mais memória que a versão não direcionada?

Infelizmente, não consigo encontrar muita coisa nos gráficos de expansão direcionados. Na verdade, basicamente tudo o que pude encontrar foi /math/2628930/how-can-one-construct-a-directed-expander-graph-with-varying-degree-distribution (que não foi respondido) e https://repository.upenn.edu/cgi/viewcontent.cgi?article=1202&context=cis_papers . Existe um termo diferente em que devo procurar?

Alex Meiburg
fonte
3
Este papel dá uma visão sobre a extensão para G = R G : people.seas.harvard.edu/~salil/research/regular-abs.htmlL=SLL=RL
sdcvvc
2
Veja o ponto 3. aqui . Você pode argumentar que é uma especulação completa, mas observe que a resposta de Scott basicamente faz o mesmo ponto sobre a exploração aleatória de gráficos direcionados.
Thomas Klimpel

Respostas:

19

O problema central é que, em gráficos direcionados, mesmo uma caminhada verdadeiramente aleatória não atinge todos os vértices no tempo polinomial esperado, muito menos uma caminhada pseudo-aleatória. O contra-exemplo padrão aqui é um gráfico direcionado com vértices ordenados da esquerda para a direita, onde cada vértice tem uma aresta que leva ao vértice à sua direita (exceto para o vértice mais à direita, t ), e cada vértice também tem uma aresta que lidera todos os caminho de volta ao vértice mais à esquerda, s . Para ir de s para t por um passeio aleatório, em seguida, leva ~ 2 n tempo. Então, qual é o algoritmo aleatório de espaço pequeno para conectividade direcionada que esperamos desaerizar, análogo ao que Reingold fez porntsst2n ? (Para colocar de outra forma, como podemos mostrar R L = N L , muito menos L = N L ?) Para a conectividade dirigido, é claro que há o algoritmo de Savitch, mas que leva O ( log 2 n ) espaço, e por gráficos gerais ninguém conseguiu melhorá-lo por meio século, com ou sem o uso da aleatoriedade.USTCONRL=NLL=NLO(log2n)

Scott Aaronson
fonte
O tipo de algoritmo que eu descreveria seria, grosso modo - bem, você executa a operação "quadrado e zig-zag" de Reingold algumas vezes para iniciar. Suponho que a modificação seria que, em vez do quadrado que contém apenas caminhos de comprimento 2 no gráfico original, ele inclui caminhos de comprimento 1 e 2. Tente todas as seqüências logaritmicamente profundas, como a dele. Se numerarmos os vértices do seu gráfico como 1, 2, .. n, o primeiro gráfico 'quadrado' conectará 1 a 2 e 3, o próximo 'quadrado' o conectará a 2345, etc. baixo. Obviamente áspero, mas não vejo por que falha.
Alex Meiburg
n2Θ(logn)n2Θ(logn)logn