1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Apass.Jack Apr 6 at 3:46
  • $\begingroup$ 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 $\endgroup$ – Sudix Apr 6 at 3:50
  • $\begingroup$ The restriction to integers does matter. What can go bad? A non-integer solution may not correspond to an integer solution. $\endgroup$ – Apass.Jack Apr 6 at 3:54
  • $\begingroup$ I am arguing that (if all paths have unique weight) there is no non-integer solution. $\endgroup$ – Sudix Apr 6 at 3:58
  • 1
    $\begingroup$ 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 $\endgroup$ – Sudix Apr 6 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.