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?


2 Answers 2


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.

  • 1
    $\begingroup$ Neat, thanks. So if I wanted to formally prove $DHP \preceq ProblemAbove$ where I have to start with an instance $G,s,t$ for the Hamiltonian Path and map it to an instance $G',s',t'$ of this problem, could I do the following: Color all existing vertices red, add $|V\setminus\{s,t\}|-1$ blue vertices and connect them in a chain $(b_1)\rightarrow \ldots \rightarrow(b_n)$. Add an edge $(s,b_1)$, and for each $(s,v)$ in $G$ an edge $(b_n,v)$ in $G'$, the rest stays as it is. $\endgroup$ Commented Apr 3, 2019 at 14:02
  • 1
    $\begingroup$ Yes I am not very familiar with NP-completeness demonstration but this way to present it is clearly better. I would nevertheless start with an instance of $G$ without $s$ & $t$ as initial Hamiltonian path problem has no specific vertex. $\endgroup$
    – Optidad
    Commented Apr 3, 2019 at 14:26
  • 2
    $\begingroup$ Upvoted for (I think) correctness; but this argument would be WAY easier to understand if you STARTED with the arbitrary graph $G'$ and then embedded it within the specially constructed $G$. Right now the reduction is hiding entirely in the single sentence "Finally, you put any number of edges between red vertices," which I missed on my first reading. "Any number of edges" is code for "you pick any arbitrary graph $G'$ whose Hamiltonian path you'd like to discover, and embed it in there." That's what makes this a valid reduction. $\endgroup$ Commented Apr 3, 2019 at 18:45
  • 1
    $\begingroup$ @Quuxplusone you are right I edit to make it clearer. $\endgroup$
    – Optidad
    Commented Apr 4, 2019 at 7:46
  • $\begingroup$ @ValeriePoulain: Vince is right that starting and ending vertices are not given for the usual HP problem, but if they are given, your reduction needs a slight tweak: You must insert a chain of $|V \setminus \{s, t\}|-1$ blue vertices in a line along each edge between $s$ and any other red vertex. This is to prevent, e.g., a single edge from $s$ to some red vertex from being a valid solution to the constructed instance. $\endgroup$ Commented Apr 4, 2019 at 8:23

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.

enter image description here

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.