Is finding a path with more red vertices than blue vertices NP-hard?

Question

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 V\setminus \{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?

Answer 1

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.

Answer 2

This answer is based on Optidad's original answer and I feel like to make it more clear. (It meant to be in the comment but I want to illustrate with pictures.)

Hamiltonian Path problem:

Given a directed graph $G$, does it contains a Hamiltonian path?

Note that the path is allow to start at any node and end at any node. But we can define s-t Hamiltonian Path problem where the start node must be s and the end node must be t, that is

Given a directed graph $G$ and two node $s,t$ in $G$, does it contains a Hamiltonian path that starts at $s$ and ends at $t$?

The s-t Hamiltonian path problem is also NP-complete: since an algorithm that solves the s-t Hamiltonian path problem can be used to solve the Hamiltonian problem by repeatedly calling the algorithm for each ordered node pair.

Next we use the following example to show the reduction from $s$-$t$ Hamiltonian Path to OP's problem.

In the example, $G=\{V,E\}$ has an $s$-$t$ Hamiltonian path: $s\rightarrow 1\rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow t$. Then we construct an instance of OP's problem $G'$: color nodes in $V\setminus \{s,t\}=\{1,2,3,4\}$ red and for each outgoing arc from $s$, i.e., $(s,1),(s,2),(s,4)$, we insert $|V|-3=3$ blue nodes along the arc. Thus any simple path starting at $s$ contains exactly $|V|-3=3$ blue nodes and there are exactly $|V|-2=4$ red nodes in $G'$. Then it is easy to see the reduction is valid.