# 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.

## 1 Answer

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.

• It might help to go back to definitions when you "simply can't find what exactly is going wrong". The meaning of polynomial time in "Each LP-program runs in polynomial time" is very different from the meaning of polynomial time in P and NP because of the different computation models. – Apass.Jack Apr 6 at 3:46
• The restriction of $x_e$ to integer variables shouldn't be necessary (as any solution of the linear program is a flow, therefore has s-t-paths, but if it would contain multiple s-t-paths, there'd be one with lowest weight, so the other paths shouldn't be in the solution), as per explanation of my linked previous question – Sudix Apr 6 at 3:50
• The restriction to integers does matter. What can go bad? A non-integer solution may not correspond to an integer solution. – Apass.Jack Apr 6 at 3:54
• I am arguing that (if all paths have unique weight) there is no non-integer solution. – Sudix Apr 6 at 3:58
• I've found my oversight. The problem lies within it being a simple path that is searched. If one allows arbitrary paths, then the whole proof in cs.stackexchange.com/a/106421/… collapses. And inversely, none of my constraints in the linear program prevent a solution which has non-simple paths – Sudix Apr 6 at 5:45