7
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • 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$ – Valerie Poulain Apr 3 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$ – Vince Apr 3 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$ – Quuxplusone Apr 3 at 18:45
  • 1
    $\begingroup$ @Quuxplusone you are right I edit to make it clearer. $\endgroup$ – Vince Apr 4 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$ – j_random_hacker Apr 4 at 8:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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