Mrthdrb

Given a connected, directed graph $G=(V,E)$, vertices $s,t in V$ and a coloring, s.t. $s$ and $t$ are black and all other vertices are either red or blue, is it possible to find a simple path from $s$ to $t$ with more red than blue vertices in polynomial time?

I think it should be possible but our TA said this was NP-hard.

Idea for a solution:

From $G$ create $G'=(V',E')$ as follows:

• Split all $v in Vsetminus s,t$ in two vertices $v_in$ and $v_out$. $V'$ is made up of the split vertex pairs and $s$ and $t$.




• For all $e=(u,v) in E$ introduce an edge $(u_out,v_in)$. (For edge $(x,v)$ or $(u,x)$ where $x in s,t$ create edge $(x,v_in)$ or $(u_out,x)$ resp.). Also, introduce an edge $(v_in,v_out)$ for any of the split vertices. So $E'$ contains two types of edges: the ones that correspond to edges from $E$ and the ones that correspond to vertices from $V$.

Now, we introduce weights as follows:

• 
  $w((v_in,v_out)) = -1$ if the corresponding vertex $v$ was red.


• 
  $w((v_in,v_out)) = +1$ if the corresponding vertex $v$ was blue.


• 
  $w(e) = 0$ for all other edges, i.e. the ones that correspond to edges of $G$ rather than vertices.

Now, conduct an algorithm for shortest paths of your choice like Dijkstra, Bellman-Ford,... , check whether the length of the given path is $<0$ and you are done.

Why does this not work? Is it because we may have negative cycles? We could detect those with Bellman Ford but then we'd have to find the desired path with non-efficient means rendering this decision problem NP-hard?
Is there an elegant reduction to show NP-hardness?

Your solution does not work because Dijkstra and Bellman-Ford cannot interpret "simple path" feature. And they will indeed fall in any negative cycle.

I think the best to show NP-completeness, is to use the Hamiltonian path problem. Let's take a graph $G'$ of $N$ red vertices.

Then you build a graph $G$, adding $s$, $t$ and $N-1$ blue vertices to $G'$. You first chain with edges all the blues vertices from the source to the last blue one ($s$->$b_1$->$b_2$->...->$b_N-1$). Then you put edges from $b_N-1$ to every red vertex and an edge from every red vertex to $t$.

So a single path from $s$ to $t$ passes necessarly through all blue nodes ($N-1$) and then have to pass to all red nodes ($N$) to answer to

Is there a simple path in $G$ from $s$ to $t$ with more red than blue vertices ?

which is thus like answer to:

Is there an Hamiltonian path in $G'$

So your problem is indeed NP-complete.