I read about vertex cover and i can't understand why the following occurs. Tried to look and research on the site and in other places but still can't understand it.

In an undirected graph $G(V,E)$, vertex cover is a set of edges U so that every Edge in E has at least one end at U.

Defining the following function: $f(G,v)$ equals to the minimal vertex cover that v belongs to.

Why if it is possible to calculate in a polynomial time the function $g(G,v)$ and it is guaranteed that $f(G,v) -5 \leq g(G,v) \leq f(G,v) +5$ then P=NP?

(Meaning if we can estimate f in a constant boundary of +5 in a polynomial time, then P=NP?)

What i think:since vertex cover is an NP-COMPLETE language, and so is the minimal vertex cover, if it is bounded by +-5, a linear bound. then if known that $g(G,v)$ can be calculated in polynomial time and we can also show that it's boundaries are $f(G,v) - 5$ and $f(G,v)+5$, then P = NP.

So regarding minimal vertex cover, the problem is $min(f(x)| x \in vertexcover(G))$. so an algorithm for minvertexcover is: initialize {cover<-0, Edges<-0}; until there are no more edges $e \in E$ in G: 1)add u,v to cover; 2)add $e_i$ to Edges; 3)remove u,v from G and adjacent edges.

Now, since $|Edges = 2 * cover|$, then for a possible solution, meaning vertex cover that covers all the edges, that possible solution will be more than Edges, so that possible solution will be bigger than 2 * Edges.

Since that possible solution $\geq 2 * Edges$, it means that the possible solution is $\geq f(G,v) + 5$, so it is bounded. now if we can calculate $g(G,v)$ in a polynomial time, it means we can calculate the possible solution in at least 2 * polynomial time, which is still polynomial. so it means that if $g(G,v)$ can be calculated in polynomial time, and the given +-5 boundary exists, then P=NP.

How to prove it correctly and efficiently? spent long days on it and would appreciate seeing how to do it correctly


1 Answer 1


I will assume that $g(G, v)$ computes a valid vertex cover, so it can never report a more optimal solution, and does so in polynomial time. We know that vertex cover is NP-hard to approximate within a factor below 1.36: http://annals.math.princeton.edu/wp-content/uploads/annals-v162-n1-p08.pdf. Since $g(G, v)$ reports a solution at most 5 more than optimal, we can scale the graph such that $(f(G,v) + 5) / f(G, v)) \leq 1.36$, which results in $f(G, v) \geq 14$.

Furthermore, vertex cover is fixed parameter tractable in the solution size. In other words, we can compute whether $G$ admits a vertex cover of a fixed size in polynomial time. Hence, we apply the fixed parameter tractable algorithm up to $k = 13$. If no solution has been found, use $g$. We now have a polynomial time algorithm that can solve any set cover instance within a factor below 1.36 times the optimal solution, which is a contradiction unless P = NP.

Corollary: it is impossible to have a computable algorithm that outputs a vertex cover of size at most $OPT + c$, where $c \geq 0$ is a constant, in polynomial time, unless P = NP.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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