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

12

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

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).
Lior Kogan
fonte
Veja isso. Foi encontrado este artigo, que parece fazer uma redução de fluxo de custo mínimo semelhante, mas usa as características especiais da rede para resolvê-la mais rapidamente do que os algoritmos gerais de MCF.
RB

Respostas:

6

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

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)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.exee(u,xe),(xe,u),(v,xe),(xe,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.txett+(t,t+)

Etapa 3: Substitua todas as arestas pelas arestas ( a + , b - ) , ( b + , a - ) . Defina o custo dessas arestas para 0.{a,b}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.ye(s,ye),(t,ye)

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


Análise:

  • Cada fluxo de 2-valorizado de de y e é uma união de um caminho x es y e e um caminho x et y e .xeyexesyexetye
  • 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
RB
fonte
1
stvPvsQvtPQvstee
@ChandraChekuri - isso está correto, mas lembre-se de que, se o problema não tiver a restrição de comprimento, há um algoritmo muito mais simples para decidir isso - veja aqui
RB
Claro, também estou ciente dessa solução - conceitualmente é bom entender os componentes biconetados por caminhos separados, mesmo que se possa encontrar vértices de corte e componentes biconectados diretamente via DFS.
Chandra Chekuri
@RB: Obrigado. O algorihm sugerido pode ser eficaz quando l for relativamente grande, mas provavelmente é subótimo para valores relativamente pequenos de l. Acho que posso aparar G primeiro removendo qualquer vértice além do piso (l / 2) de se teto (l / 2) de t.
Lior Kogan 31/03
1
yyyexey
1

stst

O(|V|+|E|)

sVssdist(s,v)vVstVttVsolution={v:vVsVt,dist(s,v)+dist(t,v)}E[Vsolution]=(v,u)E:u,vVsolution

O(|V|+|E|)O(|Vs|+|Vt|+|E[Vs]|+|E[Vt]|)st são pequenos.

st/2

bolinho de massa mobius
fonte
3
tusvxl=4vv
Obrigado pela correção @RB. Eu editei minha resposta para observar que está errado.
mobius bolinho
1

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(n4/3)O(n4/3)O(n4/3)

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

GMB
fonte