A complexidade desse problema de caminho é conhecida?

Instância: Um gráfico não direcionado $G$ com dois vértices distintos $s\neq t$ e um número inteiro $k\geq 0$ .

Pergunta: Existe um caminho $s-t$ 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.)

cc.complexity-theory graph-algorithms Andras Farago
fonte

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

@ 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

com peso igual ao número de triângulos contendo ambos

(u, w)

$(u, w)$

u \to v \to w

$u\to v \to w$

(u, v)

$(u,v)$

(v, w)

$(v,w)$

Sasho Nikolov

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.

α

$\alpha$

α

$\alpha$

Saeed

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

e temos um triângulo

e suponha que as arestas

sejam incidentes muitos triângulos. Se usarmos uma nova aresta artificial que conecta

, contamos o triângulo

u - > v - > w - > x

$u->v->w->x$

P

$P$

u, v, w

$u,v,w$

v, w, x

$v,w,x$

v x

$vx$

u w

$uw$

u - > w

$u->w$

duas vezes. PS: Meu raciocínio novamente foi errado, porque eu pensei que nós simplesmente substituir

com o novo (multi) borda

. Se adicionarmos essas arestas artificiais para cada caminho, ele funcionará trivialmente. Parece que é NPC.

v, w, x

$v,w,x$

u - > v

$u->v$

v - > w

$v->w$

u - > w

$u->w$

Saeed

Minha ideia não funcionará - eu precisaria manter vários conjuntos e acho que haverá muitos deles.

Reinierpost

A complexidade desse problema de caminho é conhecida?

Respostas: