É difícil encontrar um caminho com mais vértices vermelhos do que vértices azuis?

Dado um gráfico direcionado conectado $G=(V,E)$vértices $s,t \in V$ e uma coloração, st $s$ e $t$são pretos e todos os outros vértices são vermelhos ou azuis , é possível encontrar um caminho simples a partir de$s$ para $t$ com mais vértices vermelhos do que azuis em tempo polinomial?

Eu acho que deveria ser possível, mas nosso TA disse que isso era difícil para o NP.

Idéia para uma solução:

De $G$ crio $G'=(V',E')$ do seguinte modo:

• Dividir tudo $v \in V\setminus \{s,t\}$ em dois vértices $v_{in}$ e $v_{out}$. $V'$ é composto pelos pares de vértices divididos e $s$ e $t$.

• Para todos $e=(u,v) \in E$ introduzir uma vantagem $(u_{out},v_{in})$. (Para borda$(x,v)$ ou $(u,x)$ Onde $x \in \{s,t\}$ criar aresta $(x,v_{in})$ ou $(u_{out},x)$resp.). Além disso, introduza uma vantagem$(v_{in},v_{out})$para qualquer um dos vértices divididos. assim$E'$ contém dois tipos de arestas: as que correspondem às arestas de $E$ e os que correspondem aos vértices de $V$.

Agora, apresentamos os pesos da seguinte forma:

• $w((v_{in},v_{out})) = -1$ se o vértice correspondente $v$estava vermelho .
• $w((v_{in},v_{out})) = +1$ se o vértice correspondente $v$era azul .
• $w(e) = 0$ para todas as outras arestas, ou seja, as que correspondem às arestas $G$ ao invés de vértices.

Agora, conduza um algoritmo para os caminhos mais curtos de sua escolha, como Dijkstra, Bellman-Ford, ..., verifique se o comprimento do caminho especificado é $<0$ e você terminou.

Por que isso não funciona? É porque podemos ter ciclos negativos? Poderíamos detectar aqueles com Bellman Ford, mas teríamos que encontrar o caminho desejado com meios não eficientes, tornando difícil esse problema de decisão? Existe uma redução elegante para mostrar a dureza NP?

Sua solução não funciona porque Dijkstra e Bellman-Ford não podem interpretar o recurso "caminho simples". E eles realmente cairão em qualquer ciclo negativo.

Eu acho que o melhor para mostrar a completude do NP é usar o problema do caminho hamiltoniano. Vamos pegar um gráfico$G'$ do $N$ vértices vermelhos.

Então você constrói um gráfico $G$adicionando $s$, $t$ e $N-1$ vértices azuis para $G'$. Você primeiro encadeia com arestas todos os vértices azuis da origem até o último azul ($s$->$b_1$->$b_2$-> ...->$b_{N-1}$) Então você coloca arestas de$b_{N-1}$ para cada vértice vermelho e uma aresta de todo vértice vermelho para $t$.

Então, um único caminho de $s$ para $t$ passa necessariamente por todos os nós azuis ($N-1$) e, em seguida, precisa passar para todos os nós vermelhos ($N$) para responder a

Existe um caminho simples no $G$ de $s$ para $t$ com mais vértices vermelhos do que azuis?

que é, assim, uma resposta para:

Existe um caminho hamiltoniano em $G'$

Portanto, seu problema é realmente NP-completo.