Comprimento médio de st (simples) caminhos em um gráfico direcionado

Dado o fato de que enumeração - path é um problema # P-complete, poderia haver métodos eficientes que computem (ou pelo menos se aproximem) o comprimento médio do caminho - sem enumerá-los? ~~E se os caminhos tiverem permissão para revisitar vértices?~~ $s$ $t$ $s$ $t$

Resultados relevantes em gráficos especiais também podem ser úteis.

algorithms complexity-theory graphs approximation enumeration liuyu
fonte

Se caminhos puderem revisitar vértices, um caminho não simples implica que não há comprimento médio, pois o comprimento tenderá ao infinito.

s - t

$s-t$

Shaull

@ Shaull, você está certo. Eu estava pensando no tempo atingido de uma caminhada aleatória de para . Mas o comprimento médio tende ao infinito sem maiores restrições.

s

$s$

t

$t$

Liuyu

este parece ser muito avançado, recomendamos migrar para cstheory

vzn

Se bem entendi, essa pergunta pode ser do seu interesse para um gráfico especial.

9133 Juho

Parece que isso pode estar relacionado ao fluxo máximo da rede? Observe também que, para pequenos gráficos mundiais e vários outros gráficos com alguma simetria, ele tenderá ao comprimento médio do caminho . um algoritmo bastante natural, pode ser a mais curta aleatoriamente amostra - caminhos e veja o desvio padrão dos resultados.

s

$s$

t

$t$

vzn

Respostas: