Subgráfico contendo todos os nós e arestas que fazem parte de caminhos simples simples com comprimento limitado em um dígrafo

8

Nota: Postei uma pergunta semelhante sobre o gráfico não direcionado .

Dado

  • Um dígrafo sem arestas múltiplas ou loopsG
  • Um nó de origems
  • Um nó de destinot
  • Comprimento máximo do caminhol

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 .GGGstl

Observe que não preciso enumerar os caminhos.

Lior Kogan
fonte
Existem mais restrições ao seu problema? Lembre-se de que o seguinte problema é NP-completo: Dado o dígrafo e os vértices , existe um caminho que também contém ? Gs,t,v(s,t)v
Kristoffer Arnsfelt Hansen
@KristofferArnsfeltHansen, interesting! Deseja adicionar isso como resposta e fornecer uma referência para esse resultado? Parece que responde à pergunta original de forma negativa.
DW
@KristofferArnsfeltHansen: Não há mais restrições.
Lior Kogan,

Respostas:

6

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 .lNPNP

Em particular, o seguinte problema é completo: Dado um gráfico direcionado e os vértices , existe um caminho (simples) através de ?NPGs,t,v(s,t)v

Kristoffer Arnsfelt Hansen
fonte
Como ele se encaixa com a solução aceita aqui? stackoverflow.com/questions/10825249/… É NP-difícil apenas quando o gráfico é direcionado?
precisa
1
Correto, o problema acima pode ser resolvido com eficiência para a variante quando o gráfico não for direcionado, conforme descrito na resposta à qual você vincula.
Kristoffer Arnsfelt Hansen
0

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 .)estel=

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 aeEsteGs0s0st1tt1estque 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 destste

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.)

l


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.

DW
fonte
1
Obrigado. Também veja aqui: stackoverflow.com/questions/10825249/…
Lior Kogan
1
(s,t)NP
0

GO(V+E)

sGds(v)vGsvtG(v,u)(u,v)Gdt(v)vG

vstvds(v)+dt(v)

GvGds(v)+dt(v)l(u,v)ds(u)+dt(v)l1

Mathias Rav
fonte
5
Pode retornar caminhos que não são simples (por exemplo, para o gráfico s <--> a <--> b <--> c <--> t; b <--> d: o nó d é um beco sem saída e não deve fazer parte da solução).
Lior Kogan
0

lO(2lm(n+m))l

mle

Foreach $e=(u,v)\in E$: 
a. do for $O(2^l)$ times:
  1. Compute a random partition of the vertices set $V=(S,V\setminus S)$ 
   such that $s,u\in S$, $v,t\not \in S$ (and every other vertex is in $S$ w.p. 1/2).
  2.Find the shortest path from $s$ to $u$ in the subgraph induced by $S$.
    And the shortest path from $v$ to $t$ in the subgraph of $V\setminus S$. 
  3.If the sum of distances is no more than $l-1$, add $e$ to the output graph.


lGe

uSVS2lO(2l)

Derandomização

2polylog(l)

(n,l)SO(2l+log3(l)poly(n))

RB
fonte