3
$\begingroup$

Is there a known result saying that for some constants $0 < a < b < 1$, it is NP-hard to distinguish a graph having vertex cover number at most $a \cdot n$ from a graph having vertex cover number at least $b \cdot n$? Here n is the number of vertices in the input graph. In other words, I want to know that (unless P = NP) there is no poly-time algorithm that accepts graphs with vertex-cover number at most $a \cdot n$, rejects graphs with vertex-cover number at least $b \cdot n$, and can return anything for a graph whose vertex-cover number is in between.

$\endgroup$
5
$\begingroup$

Proving hardness of this sort of gap problem is usually how hardness of approximation is proved. For vertex cover, Håstad's famous paper (Theorem 7.1.) showed what you are asking for with $a=3/4$ and $b=7/8$.

| cite | improve this answer | |
$\endgroup$

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.