<p>Proving hardness of this sort of gap problem is usually how hardness of approximation is proved. For vertex cover, Håstad's famous <a href="https://dl.acm.org/citation.cfm?id=502098" rel="noreferrer">paper</a> (Theorem 7.1.) showed what you are asking for with <span class="math-container">$a=3/4$</span> and <span class="math-container">$b=7/8$</span>.</p>

CC BY-SA 4.0
2018-12-09T06:55:38.960Z
2018-12-09T06:55:38.960Z
Sasho Nikolov
<p>Is there a known result saying that for some constants <span class="math-container">$0 &lt; a &lt; b &lt; 1$</span>, it is NP-hard to distinguish a graph having vertex cover number at most <span class="math-container">$a \cdot n$</span> from a graph having vertex cover number at least <span class="math-container">$b \cdot n$</span>? 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 <span class="math-container">$a \cdot n$</span>, rejects graphs with vertex-cover number at least <span class="math-container">$b \cdot n$</span>, and can return anything for a graph whose vertex-cover number is in between. </p>

<approximation-hardness>
Distinguising between the cases of low or high cover number
Lior Gishboliner
# Distinguising between the cases of low or high cover number

(Asked by: username_0 on 2018-12-08)

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.

**Tags:** approximation-hardness

---

## 1 answers

### Answer by username_1 on 2018-12-09. Score: 5

Proving hardness of this sort of gap problem is usually how hardness of approximation is proved. For vertex cover, Håstad's famous [paper](https://dl.acm.org/citation.cfm?id=502098) (Theorem 7.1.) showed what you are asking for with $a=3/4$ and $b=7/8$.


---

