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

## Is finding a path with more red vertices than blue vertices NP-hard?

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?

I think it should be possible but our TA said this was NP-hard.

Idea for a solution:

From $$G$$ create $$G’=(V’,E’)$$ as follows:

• Split all $$v \in V\setminus \{s,t\}$$ in two vertices $$v_{in}$$ and $$v_{out}$$. $$V’$$ is made up of the split vertex pairs and $$s$$ and $$t$$.

• For all $$e=(u,v) \in E$$ introduce an edge $$(u_{out},v_{in})$$. (For edge $$(x,v)$$ or $$(u,x)$$ where $$x \in \{s,t\}$$ create edge $$(x,v_{in})$$ or $$(u_{out},x)$$ resp.). Also, introduce an edge $$(v_{in},v_{out})$$ for any of the split vertices. So $$E’$$ contains two types of edges: the ones that correspond to edges from $$E$$ and the ones that correspond to vertices from $$V$$.

Now, we introduce weights as follows:

• $$w((v_{in},v_{out})) = -1$$ if the corresponding vertex $$v$$ was red.
• $$w((v_{in},v_{out})) = +1$$ if the corresponding vertex $$v$$ was blue.
• $$w(e) = 0$$ for all other edges, i.e. the ones that correspond to edges of $$G$$ rather than vertices.

Now, conduct an algorithm for shortest paths of your choice like Dijkstra, Bellman-Ford,… , check whether the length of the given path is $$<0$$ and you are done.

Why does this not work? Is it because we may have negative cycles? We could detect those with Bellman Ford but then we’d have to find the desired path with non-efficient means rendering this decision problem NP-hard? Is there an elegant reduction to show NP-hardness?

## Where f(n) = n! belongs to? P, co-P, NPComplete or NPHard? [duplicate]

• What is the definition of $P$ , $NP$ , $NP$ -complete and $NP$ -hard? 6 answers
• What is the difference between an algorithm, a language and a problem? 1 answer

Where f(n) = n! belongs to? P, co-P, NPComplete or NPHard?

## NP-hard in what parameter?

I often read statements such as “the run-time of algorithm X is polynomial in m and n“. Indeed, when a problem has two parameters, it is possible that the run-time of an algorithm is polynomial in one parameter but not the other one, so if this is not the case, it is important to emphasize that it is polynomial in both parameters.

However, I have never read a statement such as “the problem is NP-hard in m and n“. A problem is always claimed to be NP-hard, period. My first question is: why? Apparently the same rationale is true here too: a problem may be NP-hard in one parameter, but at the same time, it may have an algorithm with run-time polynomial in the other parameter.

My second question: what is an accurate description of a problem with two parameters: $$m$$ and $$n$$, that (1) for a fixed $$m$$, can be solved in time polynomial in $$n$$, (2) for a fixed $$n$$, it is NP-hard (with respect to $$m$$)?

## Is there a polynomial-time reduction from a NP-hard problem to complement(tautology)?

Does someone know if this is true or false and can explain why:

If a problem X is NP-hard, then there is a polynomial-time reduction complement(tautology) <= X

## Why researchers don’t study the parameterizations of the problems unlikely to be NP-Hard?

I have seen the parameterization of the very well known problems like vertex cover, hitting set etc which are NP-hard (NP-complete precisely). Many researchers in the past have been studied the parameterization of these problems. My question is why researcher’s don’t study the parameterizations of the problems unlikely to be NP-Hard?

## Finding if a given problem is a Np-Hard problem – recruitment problem

I have to prove that the following Recruiting problem a NPC-problem.

Input: n candidates and m positions and a matrix A $$\in {Q^{n\times n}}$$. Each entry $$A_{ij}$$ with i < j tells how much gets candidates i well with candidates j. and z

Question is there m candidates so that when we sum the corresponding $$A_{ij}$$ we are able to reach z

I want only a hint how to start, i somehow did not manage to find the known NPC problem to use my reduction