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.
