Nota: Postei uma pergunta semelhante sobre o gráfico não direcionado .
Dado
- Um dígrafo sem arestas múltiplas ou loops
- Um nó de origem
- Um nó de destino
- Comprimento máximo do caminho
Estou procurando por - um subgrafo de que contém qualquer nó e qualquer aresta em (e somente aqueles) que fazem parte de pelo menos um caminho simples de para com comprimento .
Observe que não preciso enumerar os caminhos.
graph-algorithms
Lior Kogan
fonte
fonte
Respostas:
Como a pergunta é declarada, tendo como parte da entrada, o problema é -hard. Isso segue como um caso especial da classificação da classe de padrões para a qual o problema de homeomorfismo do subgrafo direcionado é concluído por artigo de Fortune, Hopcroft e Wyllie: O problema do homeomorfismo do subgrafo direcionado .l NP NP
Em particular, o seguinte problema é completo: Dado um gráfico direcionado e os vértices , existe um caminho (simples) através de ?NP G s,t,v (s,t) v
fonte
Atualização: esta resposta parece estar com defeito. Veja o comentário de Kristoffer Arnsfelt Hansen.
Não sei como resolver o seu problema, mas aqui está uma técnica para resolver uma versão mais simples do seu problema: a saber, dada a aresta , teste se existe algum caminho simples de a que inclua a aresta . (Isso corresponde ao caso especial do seu problema em que .)e s t e l=∞
Você pode resolver esse problema mais simples usando "fluxo máximo com limites inferiores" como sub-rotina. No problema de fluxo máximo padrão, a capacidade de cada aresta nos fornece um limite superior na quantidade de fluxo que passa por essa aresta, e exigimos que a quantidade de fluxo na aresta seja limitada em 0. Em "fluxo máximo com limites inferiores ", podemos especificar um limite inferior e um limite superior na quantidade de fluxo através dessa borda. Sabe-se que o "fluxo máximo com limites inferiores" pode ser resolvido em tempo polinomial.
Agora, suponha que tenhamos uma aresta e queremos testar se existe um caminho simples de a que inclua a aresta . Vamos configurar um problema de fluxo máximo com limites mais baixos. Particularmente, pegue o gráfico e adicione um novo nó com a borda um novo nó com a borda . Defina a capacidade (limite superior) em cada aresta 1. O limite inferior em todas as arestas será 0, exceto que o limite inferior na aresta é 1. Agora verifique se existe um fluxo viável de ae∈E s t e G s0 s0→s t1 t→t1 e s t que satisfaça todos os limites (esse teste pode ser realizado em tempo polinomial, conforme mencionado acima). Se não houver fluxo, não haverá um caminho simples de para . Se houver esse fluxo, rastrear esse fluxo gera um caminho simples des t s t e
Aprendi essa idéia no seguinte artigo:
(Certifique-se de ler a versão do relatório técnico, não a versão publicada. Essa ideia é encontrada no segundo parágrafo da introdução.)
Como alternativa, poderíamos resolver seu problema de maneira direta usando a programação linear inteira (ILP). Na prática, os solucionadores de ILP são muito bons em muitos problemas. No entanto, o pior tempo de execução ainda é exponencial, portanto, isso não dará um algoritmo com o pior tempo de execução polinomial. Deixe-me saber se você deseja que eu elabore como formular isso usando o ILP.
fonte
fonte
Derandomização
fonte