Complexidade da conectividade st exclusiva

Gostaria de saber se o seguinte problema pode ser decidido em (logspace nondeterministic):$\mathsf{NL}$

Dado um gráfico direcionado com dois vértices distintos s e t , existe um caminho único de s para t em G ?$G$$s$$t$$s$$t$$G$

Eu sinto que é provável que seja em , uma vez que pode decidir tanto se há um s - t -caminho e se não há tal caminho. No entanto, contar o número de tais caminhos é ♯ P- hard (Valiant, 1979).$\mathsf{NL}$$s$$t$$\mathsf{\sharp P}$

Então, minhas perguntas: você tem referências sobre isso? É óbvio que é em ? Ou que ele não está na N L ?$\mathsf{NL}$$\mathsf{NL}$

Parece que seu problema está no . Aqui está um algoritmo.$NL$

Primeiro, adivinhe não deterministicamente um caminho de para t . Se você adivinhar incorretamente, rejeite . Chame esse algoritmo A .$s$$t$$A$

Considere o seguinte algoritmo não determinístico , que determina se existem pelo menos dois caminhos. Dado um gráfico es , t , para todos os pares de arestas distintas e , f , adivinhe um caminho de s para t que inclua e, mas não f , adivinhe um caminho de s para t que inclua f, mas não e . Se as suposições estiverem corretas, aceite . Se não ocorrer aceitação para todas as opções de e e f , rejeitar . Nota $B$$s,t$$e,f$$s$$t$$e$$f$$s$$t$$f$$e$$e$$f$$B$ é implementável no espaço de registro não determinístico.

Agora, o conjunto é o conjunto de gráficos s - t com pelo menos dois caminhos de s a t . Como N L = c o N L , o complemento de B também está em N L , ou seja, podemos determinar se s e t têm menos de dois caminhos, no espaço de registro não determinístico.$L(B)$$s$$t$$s$$t$$NL = coNL$$B$$NL$$s$$t$

O algoritmo final é: "Execute Se A aceitar, execute o complemento de B e dê sua resposta".$A$$A$$B$

Eu não sei de uma referência.

ATUALIZAÇÃO: Se você realmente deseja uma referência, consulte o primeiro parágrafo da Seção 3 deste documento . Mas esta é provavelmente apenas uma das muitas referências que citam essa consequência. Seria mais razoável chamar o resultado de "folclore", em vez de citar um artigo que o menciona.

ATUALIZAÇÃO 2: Suponhamos que você queira determinar se existe um caminho simples e único. Nesse caso, o algoritmo não precisa ser alterado: se existe um caminho, existe um caminho simples. Eu acredito que a seguinte modificação vai trabalhar para o algoritmo B .$A$$B$

Queremos reescrever o algoritmo para que ele aceite se houver pelo menos dois caminhos simples.$B$

Primeiro, considere o seguinte algoritmo de tempo polinomial para o problema. Encontre o caminho mais curto de s para t . Para cada aresta e em P , verifique se há outro caminho s - t que não passa por e . Se você encontrar esse caminho, aceite . Se você nunca encontrar outro caminho, rejeite . Como P é o mais curto, ele não possui um ciclo e, se houver outro caminho que não use alguma aresta de P , haverá outro caminho que é simples e não usa alguma aresta de $P$$s$$t$$e$$P$$s$$t$$e$$P$$P$$P$. (Este algoritmo é usado para o problema do "segundo caminho mais curto".)

Vamos implementar este algoritmo em . Se tivéssemos uma N L algoritmo para consultar o bordas e em um caminho fixo P , que pode implementar o acima em logspace nondeterministic: a iteração através de todas as arestas e em P , adivinhar um s - t caminho e verificar que, para cada aresta visitado ao longo da Dessa forma, nenhum deles é igual a e .$NL$$NL$$e$$P$$e$$P$$s$$t$$e$

Então o que precisamos é um "oráculo caminho", um algoritmo com a propriedade: dada i = 1 , ... , n , em cada caminho computação algoritmo quer relata o i th vantagem sobre um determinado fixo s - t caminho ou rejeitar . Podemos obter um oráculo de caminho usando N L = c o N L para isolar o primeiro caminho lexicograficamente.$NL$$i=1,\ldots,n$$i$$s$$t$$NL=coNL$

Aqui está um esboço do caminho oracle.

Encontrar , o comprimento do caminho mais curto de s a t , por tentar todos k = 1 , ... , n e usando N G = C O N G .$k$$s$$t$$k=1,\ldots,n$$NL=coNL$

Defina as variáveis , x : = 1 , j : = k .$u:=s$$x:=1$$j:=k$

Para todos os vizinhos de u em ordem lexicográfica,$v$$u$

Determine se existe ou não um caminho de até t de comprimento j - 1 (usando o resultado N L = c o N L ). Mais precisamente, execute o algoritmo não determinístico para conectividade s - t (de comprimento j - 1 ) e o algoritmo para seu complemento, simultaneamente. Quando um deles aceitar, vá com sua resposta (deve estar correto; ambos não podem aceitar). Se ambos rejeitarem, então rejeite .$v$$t$$j-1$$NL=coNL$$s$$t$$j-1$

Se não houver caminho, prossiga para o próximo vizinho. Se você esgotou todos os vizinhos, rejeite .

Se existe um caminho, em seguida, se , de saída ( u , v ) como o i th vantagem sobre o caminho de s a t . Caso contrário, incremente x , diminua j , defina u : = v e inicie o loop for novamente se v ≠ t .$x=i$$(u,v)$$i$$s$$t$$x$$j$$u := v$$v \neq t$

Se após atingir t produz um resultado ruim i (o dado i era muito grande).$x < i$$t$$i$$i$

Dado , esse algoritmo gera a i- ésima aresta no caminho lexicograficamente mais curto P, de s para t , ou rejeita.$i$$i$$P$$s$$t$