Seja um gráfico simples não direcionado e sejam vértices distintos. Deixe que o comprimento de um caminho simples seja o número de arestas no caminho. Estou interessado em calcular o tamanho máximo de um conjunto de caminhos st simples, de modo que cada caminho tenha um comprimento ímpar, e os conjuntos de vértices de cada par de caminhos se interceptem em pares apenas em s e t. Em outras palavras, estou procurando o número máximo de caminhos st de comprimento ímpar interno e sem vértices. Eu acho que isso deve ser computável em tempo polinomial por técnicas de correspondência ou baseadas em fluxo, mas não consegui criar um algoritmo. Aqui está o que eu sei do problema.
Podemos substituir a restrição de comprimento ímpar por comprimento par; isso realmente não afeta o problema, pois um se transforma no outro se subdividirmos todas as arestas incidentes em s.
Se não houver restrição à paridade dos caminhos, o teorema de Menger fornece a resposta, que pode ser obtida calculando-se um fluxo máximo.
O problema de determinar o número máximo de ciclos de comprimento ímpar separado do vértice que se cruzam em pares apenas em um determinado vértice v é computável no tempo polinomial por um truque de correspondência: construa um gráfico G 'como a união separada de e , adicionando arestas entre duas cópias do mesmo vértice; uma correspondência máxima neste gráfico de tamanho implica que o número máximo de ciclos ímpares através de é ; essa construção é descrita na prova do Lema 11 de Na variante ímpar-menor da conjectura de Hadwiger .
Se o gráfico for direcionado, o teste da existência de um único caminho st de comprimento par já estará NP completo.
O artigo O problema do caminho par para gráficos e dígitos de Lapaugh e Papadimitriou pode ser relevante, mas infelizmente nossa biblioteca não assina o arquivo on-line e não temos uma cópia em papel.
Quaisquer informações serão muito apreciadas!
fonte
Respostas:
Observe primeiro que: dado um gráfico , dois vértices distintos e um número inteiro , o problema de decidir se existem caminhos de comprimento ímpares internamente separados por vértices entre e é polinomialmente equivalente a decidir se existem caminhos de comprimento par entre e . A redução é fácil. Para reduzir de um caso para outro, basta subdividir cada aresta adjacente a . Seja o gráfico obtido. Então tem caminhos de comprimento ímpares-disjuntos de comprimento ímpar entres , t ∈ V k k s t k s t t L ' L k s t L ' k s tG=(V,E) s,t∈V k k s t k s t t G′ G k s e se tiver caminhos de comprimento par-separado de vértices entre e .t G′ k s t
Portanto, se um desses problemas for NP-completo, o outro também. Agora Itai, Perl e Shiloach mostram que o problema de decidir se existem caminhos vértice-disjuntos de comprimento cinco entre e é NP-completo [ A complexidade de encontrar caminhos máximas disjuntos com restrições de comprimento . Networks, Volume 12, Edição 3, páginas 277–286, 1982.] A redução é de 3SAT e no gráfico construído, os caminhos de comprimento ímpares entre e têm comprimento exatamente cinco. Daí o problema de caminhos de comprimento ímpares separados por vértices em NP-complete e os caminhos de comprimento pares verticais e disjuntos.s t s tk s t s t
Espero que isto ajude.
fonte
(Não é uma resposta, mas ainda não posso comentar). Acho que a resposta acima não funciona, porque não garante que os caminhos sejam separados por vértices. Um caminho poderia usar u 'e o outro u "em G'; em G, eles usariam o mesmo vértice u.
fonte