A complexidade desse problema de caminho é conhecida?

9

Instância: Um gráfico não direcionado G com dois vértices distintos st e um número inteiro k0 .

Pergunta: Existe um caminho st em G , de modo que o caminho cruze no máximo k triângulos? (Para esse problema, diz-se que um caminho intercepta um triângulo se o caminho contiver pelo menos uma aresta do triângulo.)

Andras Farago
fonte
3
Isso está errado? Atribuímos peso a cada aresta e, em seguida, encontramos o caminho mais curto. O peso de cada aresta é o número de triângulos que incluem essa aresta. O peso desse caminho não é igual ao número de triângulos que ele encontra, mas é um primeiro caminho com número mínimo de triângulos. (O possível problema é que podemos contar um ou mais triângulos duas vezes porque visitamos duas arestas desse triângulo, mas a razão pela qual as escolhemos é que elas são menores do que atravessar a outra aresta do triângulo e também temos meios de caminho simples duas arestas de um triângulo estão próximas uma da outra).
Saeed
3
@ Saeed eu não entendo: qual é o argumento de que a contagem excessiva não faz você escolher um caminho abaixo do ideal? Seu algoritmo é certamente uma aproximação de 2. Talvez uma correção seja adicionar uma aresta para cada caminho u v w com peso igual ao número de triângulos contendo ambos ( u , v ) e ( v , w )(u,w)uvw(u,v)(v,w)
Sasho Nikolov
2
Certo, podemos ir de u para ve, em seguida, escolhemos x (algum outro nó que não está no triângulo uvw) e depois vamos para w, o que está errado (meu erro foi ter perdido os vértices que não estão no triângulo uvw) , mas com sua correção, está correto, pois para cada caminho st com triângulos no gráfico original, há um caminho de peso α no gráfico auxiliar. Além disso, o peso do caminho no novo gráfico é sempre pelo menos o número de triângulos no caminho correspondente no gráfico original. αα
Saeed
11
Penso um pouco mais sobre isso, mesmo após a correção não funciona. Desculpe Andras se eu trouxe uma esperança errada. Para ver por que a correção está errada, considere os vértices em um caminho P e temos um triângulo u , v , w e v , w , x e suponha que as arestas v x e u w também sejam incidentes muitos triângulos. Se usarmos uma nova aresta artificial que conecta u - > w , contamos o triângulo vu>v>w>xPu,v,wv,w,xvxuwu>w duas vezes. PS: Meu raciocínio novamente foi errado, porque eu pensei que nós simplesmente substituir u - > v e v - > w com o novo (multi) borda u - > w . Se adicionarmos essas arestas artificiais para cada caminho, ele funcionará trivialmente. Parece que é NPC. v,w,xu>vv>wu>w
Saeed
11
Minha ideia não funcionará - eu precisaria manter vários conjuntos e acho que haverá muitos deles.
Reinierpost

Respostas:

1

Suponha não existem auto-bordas em .G

vivjGE[i,j]=1E[i,j]=0n×nC[i,j]=k=1nE[i,k]E[k,j]vivjvivjGD[i,j]=E[i,j]C[i,j]D[i,j]=CO(n3)G

n×nAA[i,j]=min(D[i,j],mink(D[i,k]+D[k,j]E[i,j]))AD

Agora apenas calcule o caminho mais curto entre e em em um novo gráfico do qual é a matriz de adjacência (ponderada) usando Dijkstra (já que todos os pesos das arestas são positivos), e determine se , onde é o fechamento sobre a semicondução tropical (que fornece a matriz de distância).vivjGAA[i,j]kA

Edgar
fonte