Overview Link to heading

Given an unknown Problem B, how can we show that it is NP-Complete?

To accomplish this, we do the following:

1. Show that problem B is in the class of NP problems.

We are given a candidate solution to an instance of our unknown Problem B, and we show that we can validate that solution in polynomial time. We are not solving the problem, we are checking that the candidate solution is in fact a complete and valid solution.

Formally, if given an instance I and solution S, we can verify S is a solution to I in polynomial time with respect to the size of I. Be extra careful if there is a goal (g), target (k), or budget (b) given. Do not make the runtime dependent on this value or we will end up with a pseudo polynomial verification.

2. Show that problem B is at least as hard as a problem known to be NP-Complete.

This is done via reduction from a known problem A (A → B):

Algorithm for A
Instance f(I)
Solution S of f(I)
Solution h(S) of I
No solution to f(I)
Algorithm for B
f
h
Instance I
Solution to I
No solution to I

The specific steps are as follows:

Input transformation: Show how any instance of Problem A is converted to an instance of Problem B in polynomial time. This is the function f, which yields the instance f(I) to Problem B.

Output transformation: Show how a solution S to Problem B is converted to a solution for Problem A, again in polynomial time. This is the function h, which yields the solution h(S) for Problem A.

Correctness proof: Show that a solution for B exists if-and-only-if a solution to A exists. We must prove both directions – if we have a solution to instance f(I) for B, we have a solution to instance I of A; and if there is no solution for B, then no solution exists for A. This is where we explain why our reduction works – what is it about the input & output transformations which guarantee that the unknown problem is solved only if the known problem is solved, and that a solution to the unknown problem guarantees a solution to the known problem.

Examples Link to heading

The following examples demonstrate NP-Complete problems across different domains: graph theory, boolean satisfiability (SAT), and knapsack.

For NP-Complete reductions, we can use any problems shown to be NP-Hard or NP-Complete in the following list:

  • SAT
  • 3SAT
  • Clique
  • Independent Set (IS)
  • Vertex Cover (VC)
  • Subset Sum (SSS)
  • Rudrata (s, t)-Path
  • Rudrata Cycle
  • Integer Linear Programming (ILP)
  • Traveling Salesman Problem (TSP)

Graph Theory Link to heading

Problem Link to heading

A Kite is a graph on an even number of vertices, say 2n, in which n of the vertices form a clique and the remaining n vertices are connected in a “tail” that consists of a path joined to one of the vertices of the clique. Given a graph and a goal g, the Kite problem asks for a subgraph which is a kite and which contains 2g nodes. Prove that Kite is NP-complete

Solution Link to heading

1. Proving Kite is in NP

Given a potential solution subgraph S, we can verify its validity in polynomial time by:

  • Checking if |S| = 2g (takes O(n) time)
  • Verifying that g vertices form a clique by:
    • Counting degrees of all vertices (O(n + m) time)
    • Ensuring g vertices have at least (g-1) degrees
    • Confirming these vertices form a complete subgraph (O(n²) time)
  • Verifying the remaining g vertices form a tail by:
    • Identifying vertices with degrees ≤ 2 (O(n) time)
    • Using BFS to ensure the subgraph is connected (O(n + m) time)

The total verification time is O(n²), which is polynomial.

2. Reduction from Clique to Kite

We now show that Kite is at least as hard as Clique by reducing Clique to Kite in polynomial time.

Input transformation:

Given a Clique problem instance (G=(V,E), g), we create a new graph G’ such that we add a unique tail of g vertices to each vertex in V.

Pass G’ and g to Kite.

It takes O(n) to add a tail for each vertice, overall O(n^2).

Output transformation:

  • If Kite returns No, we return No for Clique. This takes O(1) time
  • If Kite returns a solution, we:
    • Remove all vertices with degree < (g-1)
    • Return the remaining vertices as the Clique solution
    • This takes O(n + m) time

Note: We cannot simply remove the newly-added tail vertices because the original graph G might have contained a valid kite structure.

Correctness proof:

  • If a solution to Clique exists, because we attached a unique g-sized tail to all vertices, there now must exist a clique with a tail in G’ for Kite.
  • If there is no solution to Clique, then since our added tails cannot possibly create a clique, there can be no clique in G’ to form the solution for Kite.

SAT Link to heading

Problem Link to heading

In the Exact-4SAT problem, the input is a set of clauses, each of which is a disjunction of exactly four literals, and such that each variable occurs at most once in each clause. The goal is to find a satisfying assignment, if one exists. Prove that Exact-4SAT is NP-complete.

Solution Link to heading

1. Proving Exact-4SAT is in NP

Given a potential solution (truth assignment) S, we can verify its validity in polynomial time by:

  • Checking each clause to ensure at least one literal is satisfied
  • Since each clause has exactly 4 literals, checking a clause takes O(1) time
  • For m clauses, the total verification time is O(m), which is polynomial

2. Reduction from 3SAT to Exact-4SAT

We now show that Exact-4SAT is at least as hard as 3SAT by reducing 3SAT to Exact-4SAT in polynomial time.

Input transformation:

Given a 3SAT instance with clauses C, we transform it to an Exact-4SAT instance as follows:

First, we handle any single-literal clauses by setting them to true and simplifying the CNF formula. This leaves us with clauses containing either 2 or 3 literals.

For each clause c in C:

  • If c has 2 literals (l₁, l₂), we replace by 4 new clauses:
    • (x ∨ y ∨ l₁ ∨ l₂)
    • (¬x ∨ y ∨ l₁ ∨ l₂)
    • (x ∨ ¬y ∨ l₁ ∨ l₂)
    • (¬x ∨ ¬y ∨ l₁ ∨ l₂)
  • If c has 3 literals (l₁, l₂, l₃), we replace by 2 new clauses:
    • (x ∨ l₁ ∨ l₂ ∨ l₃)
    • (¬x ∨ l₁ ∨ l₂ ∨ l₃)

The transformation adds 1 or 2 new variables (x and y) and 2 or 4 new clauses for each original clause, taking O(m) time.

Output transformation:

  • If Exact-4SAT returns No, we return No for 3SAT. This takes O(1) time
  • If Exact-4SAT returns a solution, we:
    • Remove the newly added variables (x and y)
    • Return the remaining variable assignments as the 3SAT solution
    • This takes O(m) time

Correctness proof:

  • For clauses with 3 literals (l₁, l₂, l₃):

    • If x is true, then (x ∨ l₁ ∨ l₂ ∨ l₃) is satisfied, and (¬x ∨ l₁ ∨ l₂ ∨ l₃) requires (l₁ ∨ l₂ ∨ l₃) to be satisfied
    • If x is false, then (¬x ∨ l₁ ∨ l₂ ∨ l₃) is satisfied, and (x ∨ l₁ ∨ l₂ ∨ l₃) requires (l₁ ∨ l₂ ∨ l₃) to be satisfied
    • In both cases, the original 3SAT clause must be satisfied

  • For clauses with 2 literals (l₁, l₂):

    • The four new clauses ensure that regardless of the values of x and y, at least one of l₁ or l₂ must be true
    • This maintains the satisfiability of the original 2-literal clause

Therefore, a solution exists for the 3SAT instance if and only if a solution exists for the Exact-4SAT instance.

Knapsack Link to heading

Problem Link to heading

Consider the Knapsack-search problem.

Input: integer weights w₁, w₂, …, wₙ and integer values v₁, v₂, …, vₙ for n items. We are also given a weight capacity W and a goal g.

Output: a subset of items whose total weight is at most W and whose total value is at least g, or report No if such a set does not exist.

Prove that Knapsack-search is NP-complete.

Solution Link to heading

1. Proving Knapsack-search is in NP

We first demonstrate that Knapsack-search is in the class NP. Given an input of integer weights w₁, w₂, …, wₙ and integer values v₁, v₂, …, vₙ for n items, a weight capacity W and a goal g, and a candidate solution S, we can verify it in polynomial time as follow:

  • Compute the total weight W_S of items in solution S. It takes O(n).
  • Compute the total value V_S of items in solution S. It takes O(n).
  • Compare W_S to W and V_S to g. It takes O(1). Overall, the runtime is O(n), which is polynomial.

2. Reduction from Subset Sum to Knapsack-search

We now show that Knapsack-search is at least as hard as Subset Sum by reducing Subset Sum to Knapsack-search in polynomial time.

Input transformation:

Given an input set of n integers a₁, a₂, …, aₙ and a target sum T for Subset Sum.

Set a₁ = w₁ = v₁, a₂ = w₂ = v₂, …, aₙ = wₙ = vₙ for 1 ≤ i ≤ n.

Set T = W = g.

Pass w₁, v₁, w₂, v₂, …, wₙ, vₙ, W and g into the Knapsack-search algorithm.

Overall, it takes O(n) time to transform input and this is polynomial.

Output transformation:

If the Knapsack-search returns No, we return No for the Subset Sum. This takes O(1).

If the Knapsack-search returns a subset S, for each item in subset S, set aᵢ = wᵢ to form S’. Return S’ for the Subset Sum. This takes O(n).

Correctness proof:

If Subset Sum finds a solution, a solution must exist for Knapsack-search.

If there exists a subset S for Subset Sum such that total sum = T, by setting aᵢ = wᵢ = vᵢ for 1 ≤ i ≤ n, we enforce the total weight W ≤ T and total value g ≥ T. So S satifies Knapsack-search.

If Knapsack-search finds a solution, a solution must exist for Subset Sum.

If the subset S satisfies the total W ≤ T and total value g ≥ T, and since wᵢ = vᵢ for 1 ≤ i ≤ n, it means W = g = T. By mapping wᵢ back to aᵢ to form S’, we ensure that S’ is a valid Subset Sum solution.