Subgráfico contendo todos os nós e arestas que fazem parte de caminhos simples simples com comprimento limitado em um gráfico não direcionado

Muito semelhante à minha pergunta postada anteriormente . Desta vez, no entanto, o gráfico não é direcionado.

Dado

• Um gráfico não direcionado sem arestas múltiplas ou loops,$G$
• Um vértice de origem ,$s$
• Um vértice alvo ,$t$
• Comprimento máximo do caminho ,$l$

Estou procurando por - Um subgrafo de G que contém qualquer vértice e qualquer aresta em G (e somente aqueles) que fazem parte de pelo menos um caminho simples de s a t com comprimento ≤ l .$G'$$G$$G$$s$$t$$\leq l$

Notas:

• Não preciso enumerar os caminhos.
• Estou procurando um algoritmo eficiente (tempo e memória), pois preciso executá-lo em gráficos muito grandes (10 ^ 8 vértices, 10 ^ 9 bordas).

Bem, o problema está em afinal. Vou manter a resposta anterior , uma vez que também funciona para o caso dirigido (que é NPC, como respondida na outra questão), e mostra que é F P T com relação a l .$P$$FPT$$l$

No caso não direcionado, é solucionável, deterministicamente, por meio do fluxo de custo mínimo (isso pode não funcionar nas escalas a que você está se referindo na pergunta, mas é melhor que o algoritmo exponencial.

O procedimento a seguir decidirá se alguma aresta deve fazer parte do gráfico de saída. Para responder ao problema original, faça um loop em todas as bordas.$e=(u,v)\in E$

Para criar a rede de fluxo, faça o seguinte:

Passo 1: Expand ter um vértice x e e substituir e com as arestas ( u , x e ) , ( x e , u ) , ( v , x e ) , ( x e , v ) (que são dirigidos como um parte da rede de fluxo), defina seu custo como 0.$e$$x_e$$e$$(u,x_e),$$(x_e,u),(v,x_e),(x_e,v)$

Etapa 2: substitua todos os vértices , exceto x e por dois vértices t - e t + , e adicione uma aresta ( t - , t + ) . Defina o custo dessas arestas como 1.$t$$x_e$$t^-$$t^+$$(t^-,t^+)$

Etapa 3: Substitua todas as arestas pelas arestas ( a + , b - ) , ( b + , a - ) . Defina o custo dessas arestas para 0.$\{a,b\}\in E$$(a^+,b^-),(b^+,a^-)$

Passo 4: Adicionar um novo vértice e adicionar as bordas ( s , y e ) , ( t , y e ) com custo 0.$y_e$$(s,y_e),(t,y_e)$

Etapa 5: defina todas as capacidades para 1.

Agora execute o algoritmo de fluxo de custo mínimo, procurando um fluxo de valor 2 de para y e .$x_e$$y_e$

Análise:

• Cada fluxo de 2-valorizado de de y e é uma união de um caminho x e ⇝ s → y e e um caminho x e ⇝ t → y e .$x_e$$y_e$$x_e\leadsto s\to y_e$$x_e\leadsto t\to y_e$
• Os caminhos são disjuntos, pois para cada vértice há apenas 1 capacidade no arco ( t - , t + ) .$t$$(t^-,t^+)$
• Os caminhos retornados são os dois caminhos cuja soma das distâncias é mínima e esse também é o custo do fluxo encontrado. Isso nos permite adicionar ao gráfico de saída ou excluir caso contrário.$e$

$s$$t$$s$$t$$\le \ell$

$O(|V|+|E|)$$\ell$

$s$$\ell$$V_s$$s$$\ell$$dist(s,v)$$v \in V_s$$t$$V_t$$t$$V_{solution}=\{ v : v \in V_s \cap V_t, dist(s,v)+dist(t,v) \le \ell \}$$E[V_{solution}]$$=(v,u) \in E : u,v \in V_{solution}$

$O(|V|+|E|)$$O(|V_s| + |V_t| + |E[V_s]|+|E[V_t]|)$$\ell$$s$$t$ são pequenos.

$s$$t$$\ell/2$$\ell$$\ell$

Isso pretende ser um comentário, mas é muito longo para ser postado como um comentário.

$G = (V, E)$$H = (V, E')$$H = (V, E', w)$

$O(n^{4/3})$$O(n^{4/3})$$O(n^{4/3})$

Se isso parecer útil, posso tentar desenterrar as construções relevantes para você.