Skip to main content
added 18 characters in body
Source Link
Optidad
  • 1.8k
  • 1
  • 9
  • 12

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.

Let'sThen you build a graph $G$ with, adding $N+1$ red vertices$s$, $t$ and $N$$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 between this last onefrom $b_{N-1}$ to every red vertex and an edge from every red vertex to the sink. Finally, you put any number of edges between red vertices$t$.

So a single path from $s$ to $t$ passes necessarly through all blue nodes. Answering ($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 answeringanswer to:

Is there an Hamiltonian path in $G'$

with $G'$, the subgraph containing only red vertices.

And thisSo your problem is known asindeed NP-complete.

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 build a graph $G$ with $N+1$ red vertices and $N$ blue vertices. You first chain with edges all the blues vertices from the source to the last blue one. Then you put edges between this last one to every red vertex and an edge from every red vertex to the sink. Finally, you put any number of edges between red vertices.

So a single path from $s$ to $t$ passes necessarly through all blue nodes. Answering to

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

is like answering to:

Is there an Hamiltonian path in $G'$

with $G'$, the subgraph containing only red vertices.

And this problem is known as NP-complete.

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.

Source Link
Optidad
  • 1.8k
  • 1
  • 9
  • 12

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 build a graph $G$ with $N+1$ red vertices and $N$ blue vertices. You first chain with edges all the blues vertices from the source to the last blue one. Then you put edges between this last one to every red vertex and an edge from every red vertex to the sink. Finally, you put any number of edges between red vertices.

So a single path from $s$ to $t$ passes necessarly through all blue nodes. Answering to

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

is like answering to:

Is there an Hamiltonian path in $G'$

with $G'$, the subgraph containing only red vertices.

And this problem is known as NP-complete.