Back to course

Exercise 8

NP-Hardness Proofs

Formal ProofsCounterexamplesVery Hard Difficulty

Exam Format & Expectations

NP-hardness proof questions typically ask you to:

  1. Prove a statement is true - Usually about NP-hardness
  2. Disprove with counterexample - Show the statement is false
  3. Analyze special cases - When does a hard problem become easy?

Warning: This is often the hardest exercise. Focus on finding small counterexamples or using standard proof techniques.

Standard Proof Techniques

Proving NP-Hardness

  1. 1. Start with known NP-hard problem A
  2. 2. Show reduction: A ≤p B
  3. 3. Given instance of A, construct instance of B
  4. 4. Prove: A has solution ↔ B has solution
  5. 5. Show reduction is polynomial time

Finding Counterexamples

  1. 1. Look for small instances (3-5 vertices)
  2. 2. Try edge cases (empty graph, complete graph)
  3. 3. Check special structures (star, path, cycle)
  4. 4. Verify your example carefully
  5. 5. Show why the statement fails

Past Exam Example: Weighted Vertex Cover (2024)

Statement:

"WEIGHTED-VERTEX-COVER is NP-hard: Given graph G = (V,E), vertex weights w: V → ℕ, and integer k, does G have a vertex cover of total weight ≤ k?"

Prove this statement is TRUE.

Full Solution(10/10)

Proof by reduction from VERTEX-COVER (known NP-complete):

Reduction

Given instance of VERTEX-COVER: Graph G = (V,E) and integer k.

Question: Does G have a vertex cover of size ≤ k?

Construction:

  • • Use the same graph G
  • • Set w(v) = 1 for all v ∈ V
  • • Use the same k

Correctness:

G has vertex cover S of size ≤ k

↔ |S| ≤ k↔ Σv∈S w(v) = Σv∈S 1 = |S| ≤ k

↔ G has weighted vertex cover of weight ≤ k

Time complexity: O(|V|) to assign weights. Polynomial. ✓

Since VERTEX-COVER is NP-complete, WEIGHTED-VERTEX-COVER is NP-hard.

Example: Finding a Counterexample (2023)

Statement:

"If a graph G has a Hamiltonian path, then removing any vertex from G leaves a graph with a Hamiltonian path."

Prove this statement is FALSE by giving a counterexample.

Full Solution(10/10)

Counterexample:

Consider the path graph P4 with vertices {a, b, c, d}:

a — b — c — d

1. G has a Hamiltonian path: a → b → c → d ✓

2. Remove vertex b:

Resulting graph G' has vertices {a, c, d} with edges:

a c — d

(no edge between a and c)

3. G' has NO Hamiltonian path:

  • • To visit all vertices, must include a
  • • But a has degree 0 in G'
  • • So a must be endpoint of any Hamiltonian path
  • • But can't reach both c and d from a

Therefore, the statement is FALSE. Removing vertex b from P4creates a graph with no Hamiltonian path. ✗

Common Statement Types

Type 1: Special Cases

"Problem X remains NP-hard even when restricted to graphs with property Y"

Approach: Reduce from general case, ensuring construction has property Y.

Type 2: Algorithm Claims

"This greedy/simple algorithm solves NP-hard problem X"

Approach: Almost always FALSE. Find small counterexample.

Type 3: Structural Properties

"If graph has property A, then it has property B"

Approach: Try standard graphs (path, cycle, star, complete).

Strategies for Success

Quick Checks

  • • If it claims P = NP, it's FALSE
  • • If it claims easy algorithm for NP-hard, it's FALSE
  • • Check small graphs first (n ≤ 5)
  • • Draw your examples clearly
  • • Verify edge cases

Time Management

  • • Spend max 20 minutes here
  • • If stuck, try the opposite (true → false)
  • • Small counterexamples = full points
  • • Don't overcomplicate proofs
  • • Move on if completely stuck

Exam Tip

This exercise has high variance - sometimes easy, sometimes very hard. Don't panic if you can't solve it immediately. Often, a simple 3-4 vertex counterexample is all you need.

Previous: NP-ComplexityBack to Course Overview