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?