Where's the flaw in my algorithm? (Linear program to solve NP-hard problem) The problem (copy-pasted from this question on cs.stackexchange):

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?

My algorithm:
We first add weights to the edges:

If the edge goes into a red vertex, we let its weight be -1. 
If the edge goes into a blue vertex, we let its weight be 1. 
Any edge going into $t$ has weight 0.

This way, any path from $s$ to $t$ with negative weight is a solution.

We now formulate a linear program, which finds the path with lowest weight from all paths with length $\le c$ (i.e. it only looks at paths with $\le c$ edges ):

Minimize the function:
$$ \sum_{e\in E} c_e\cdot x_e $$

Under the constraints:
$$
\forall v\in V-\{s,t\}: \sum_{e\in in(v)}x_e -\sum_{e\in out(v)} x_e = 0
\\
\sum_{e\in out(s)} x_e = 1
\\
\sum_{e\in in(t)} x_e = 1
\\
\sum_{e\in in(s)} x_e = 0
\\
\sum_{e\in out(t)} x_e = 0
\\
\sum_{e\in E} x_e \le c
\\
\forall e\in E: x_e \ge 0
$$

Here $c_e$ are the weights of the edges, $in(v)$ are all edges going into $v$, and $out(v)$ are all edges starting in $v$.

This linear program is, except for the constraint $\sum_{e\in E} x_e \le c$, identical to the one which I asked about in my previous question, and in which it is proved that that linear program indeed returns a shortest path.

Even with the newly added constraint $\sum_{e\in E} x_e \le c$ to me it looks like my previous reasoning is still valid.

If that were the case however, we could solve the linear program for $c=1,...,|E|$, and for each solution check whether its weight is negative. If we find any solution for which the weight is negative, we have a path as is requested by the problem.

If all solutions have positive weight, then there is no such path.

As each LP-program runs in polynomial time, and we have to run $|E|$ variations of this program, the whole algorithm should still be run in polynomial time.

This however clashes with the fact that the problem itself is NP-hard.

So, somewhere in my reasoning is a mistake (most likely the result of the linear program doesn't have to be a path anymore or something similar) - however, I simply can't find what exactly is going wrong. Where is it?



Edit:

The reasoning (copied from the previous question) for the correctness of the linear program:

Let $S$ be a solution to above linear program. As the constraints are the same as for network flows (if we see each edge as having infinite capacity), $S$ is a flow on $G$. 

Given that every $s-t$-path fulfills the constraints, we can conclude that if $S$  is an  $s-t$-path, then it is an $s-t$-path with minimal costs.

Further, $S$ can't contain any cycle with positive weight, as we could simply remove this cycle from $S$ and end up with a lower-cost solution that fulfills the constraints. 

Finally, $S$ has to be an $s-t$-path. Let's assume $S$ wasn't. Given that $S$ is a flow, we know that it has to contain some $s-t$-path. So let $M$ be the set of all $s-t$-paths that $S$ contains.
 Then there is a path with minimal costs in $M$ (as $S$ is cycle-free, and therefore there can only be finitely many elements in $M$). Let this $s-t$-path be $p_{min}$.

If we let $c: M\to \mathbb R $ now be the map that assigns each $s-t$-path in $M$ its cost, we obtian the following inequality:
$$1\cdot p_{min} \le \sum_{p\in M} \lambda_p \cdot p \qquad\text{ given that } \forall p\in M: \lambda_p \ge 0 , \sum_{p\in M} \lambda_p = 1$$

Therefore, if $S$ would contain multiple $s-t$-paths, it wouldn't be minimal.

Thus we can conclude, that $S$ is a minimal $s-t$-path.
In your program specification, "$\forall e\in E: x_e \ge 0$" should be "$\forall e\in E: x_e=0\text{ or } 1$". 

"Each LP-program runs in polynomial time". However, your instance is an instance of integer linear programming (ILP), which is NP-hard, even when all variables are restricted to be either 0 or 1. In particular, this answer shows that the instances of ILP as given in this question is NP-complete.