PadhaikoAll subjects

NP-Hard and NP-Complete Problems

Analysis of Algorithms (ENCT 388)

Open in the Padhaiko app

7.1 Basic concepts

Computational complexity classifies decision problems (yes/no problems) according to whether they can be solved or verified in polynomial time ( for some constant ) as a function of input encoding size .

Definition

Complexity Classes P, NP, NP-Hard, and NP-Complete

AspectP vs. NPNP-Hard vs. NP-Complete
Core Meaning: efficiently solvable; : efficiently verifiable-Complete -Hard
Membership in (whether is open)-Complete ; -Hard may lie outside
Consequence if in If any problem is in , then Proving requires showing and

7.2 Cook's theorem

Before any problem can be proved -complete by reduction from another -complete problem, one first problem had to be proved -hard directly from the definition of . Stephen Cook (1971) and Leonid Levin (1973) established this foundation using Boolean Satisfiability (SAT).

Theorem

Cook's Theorem (Cook-Levin Theorem)

The Satisfiability problem (SAT)—given a Boolean formula in conjunctive normal form (CNF), decide whether there exists a truth assignment to its variables making true—is -complete.

Proof

  1. : Given a candidate truth assignment (certificate) for the variables, substituting and evaluating every clause takes deterministic polynomial time.
  2. is -hard: Let be decided by a non-deterministic Turing machine in polynomial time on input of length . Construct in polynomial time a CNF formula over Boolean variables representing the tape cell contents, head positions, and machine states across all time steps :

Each part has size (or ), and is satisfiable if and only if has an accepting computation path on . Hence for every .

Starting from Cook's Theorem, the classic chain of polynomial reductions proves thousands of problems -complete:


7.3 NP-Hard graph problems

Many classical graph decision and optimization problems are -complete (decision form) or -hard (optimization form):

Core NP-Hard / NP-Complete Graph Problems and Reductions
ProblemDecision FormulationReduction Source
Clique (CDP)Does contain a complete subgraph of size ? (one vertex per literal, edges between non-conflicting literals in different clauses)
Vertex (Node) Cover (NCDP)Does have a subset of size touching every edge? ( has a -clique has a vertex cover of size )
Chromatic Number (CNDP)Can be properly colored using at most colors? (truth gadgets + triangle palette)
Hamiltonian Cycle (HC)Does contain a simple cycle visiting every vertex once?
Travelling Salesperson (TSP)Does a weighted complete graph have a Hamiltonian tour of cost ? (weight for edges in , for non-edges, bound )
Example 1

1 (6 marks)

Using the standard reduction , construct the graph for the -CNF formula with clauses:

and identify a -clique in along with the corresponding satisfying truth assignment.

Constructing vertices and edges of :

  • Vertices ( vertices): Create one vertex for each literal occurrence in clause :
    • Clause : , ,
    • Clause : , ,
    • Clause : , , .
  • Edges: Connect vertex and iff they belong to different clauses () and are not logical negations of each other ().

Finding a -clique and extracting the assignment: Pick one consistent literal per clause:

  • From :
  • From : (compatible with )
  • From : (compatible with both and ).

Since , , and are pairwise non-contradictory and in distinct clauses, forms a -clique in . Setting (and or ) satisfies all three clauses of .

Answer:

Graph has vertices across clause groups; the -clique maps directly to the satisfying assignment .


7.4 NP-Hard scheduling problems

Many practical processor and workshop scheduling formulations are -hard:

  1. Scheduling Identical Processors (): Given independent jobs with processing times and identical parallel processors, assign jobs to processors to minimize the makespan (maximum completion time across all processors).
    • For , deciding whether makespan is identical to the Partition problem (), proving even -processor makespan minimization is NP-hard.
  2. Job-Shop and Flow-Shop Scheduling ( machines): While -machine flow shop scheduling () is solvable in via Johnson's rule, -machine flow-shop scheduling () and general job-shop scheduling () are NP-hard (via reduction from 3-Partition).
  3. Scheduling with Deadlines and Penalties: Choosing a subset of jobs with arbitrary processing times , deadlines , and penalties to minimize total late penalty on a single machine is NP-hard (reducible from 0/1 Knapsack / Partition).

7.5 NP-Hard code generation problems

In compiler design, optimal code generation translates an intermediate expression representation into machine instructions using a fixed finite number of CPU registers so as to minimize total instructions (or memory spills).


7.6 Simplified NP-hard problems

Small structural or parameter restrictions frequently separate an -hard problem from a polynomial-time () special case ("simplified" problems):

Hard Problems vs. Simplified Polynomial-Time Counterparts
NP-Hard / NP-Complete ProblemSimplified Special Case in Reason for Tractability
3-SAT (3 literals/clause)2-SAT (2 literals/clause)Implication graph + Strongly Connected Components in
3-Colorability ()2-Colorability (Bipartiteness)Simple BFS/DFS parity check in
Hamiltonian Cycle (visit every vertex once)Eulerian Cycle (traverse every edge once)Degree parity check (all degrees even + connected) in
Longest Simple PathShortest Simple Path (non-negative weights)Dijkstra / Bellman-Ford in polynomial time
0/1 Knapsack (integer items)Fractional Knapsack (or small unary )Greedy by in
General Vertex CoverVertex Cover on Trees / Bipartite GraphsTree DP in / König's theorem via max matching
-Machine Flow Shop ()-Machine Flow Shop ()Johnson's rule in

7.7 Approximation algorithms: -approximation, polynomial time approximation scheme, probabilistically good algorithms

Because -hard optimization problems have no known polynomial-time exact algorithms (unless ), we design polynomial-time approximation algorithms with provable quality guarantees.

Definition

Approximation Ratio, PTAS, FPTAS, and Probabilistic Algorithms

Let be the optimal objective value on instance and be the value returned by a polynomial-time approximation algorithm:

  1. -Approximation Algorithm: For inputs of size , the solution stays within factor of optimal:
  1. -Approximation Algorithm: An algorithm satisfying the relative error bound for a fixed constant :

(equivalently for minimization, or for maximization).

  1. Polynomial-Time Approximation Scheme (PTAS): A family of -approximation algorithms taking any as input and running in polynomial time in for each fixed , e.g. or .
  2. Fully Polynomial-Time Approximation Scheme (FPTAS): A PTAS whose running time is polynomial in both and , e.g. .
  3. Probabilistically Good (Randomized Approximation) Algorithm: Uses random choices so that for every input instance, it runs in polynomial time and produces a solution within the desired approximation ratio (or exact optimum) with high probability (e.g., , boostable by independent repetitions).

7.8 Vertex cover problem, subset sum problem

2-Approximation Algorithm for Vertex Cover

A vertex cover of is a subset such that every edge has at least one endpoint in .

2-Approximation for Minimum Vertex Cover (Pseudocode Logic)C
// Repeatedly pick an arbitrary uncovered edge (u, v) and add BOTH u and v to C
void approxVertexCover(int V, int E, int u_edge[], int v_edge[], int inCover[]) {
    for (int i = 0; i < V; i++) inCover[i] = 0;
    for (int e = 0; e < E; e++) {
        int u = u_edge[e], v = v_edge[e];
        if (!inCover[u] && !inCover[v]) {
            inCover[u] = 1;
            inCover[v] = 1;
        }
    }
}
Theorem

2-Approximation Guarantee for Vertex Cover

approxVertexCover runs in time and returns a vertex cover of size at most , where is an optimal minimum vertex cover.

Proof

Let be the set of edges picked by the algorithm. No two edges in share an endpoint (since adding removes all edges incident to or ). Any valid vertex cover—including —must include at least one endpoint of every edge in , so . Meanwhile, the algorithm adds both endpoints of each edge in , giving .

Example 2

2 (5 marks)

Run approxVertexCover on the -vertex graph with edges (processed in that exact order), compare the output size against an optimal vertex cover , and compute the achieved approximation ratio.

Tracing approxVertexCover in edge order:

  1. Edge is uncovered add to (). Covered edges now: .
  2. Edge : vertex (already covered).
  3. Edge : vertex (already covered).
  4. Edge is uncovered () add to ().
  5. Edges and : vertices (both already covered).

Algorithm terminates with , .

Comparing with optimal : The three edges , , and are pairwise vertex-disjoint (share no endpoints), so every valid vertex cover must pick at least one vertex from each—meaning . Conversely, covers all edges with . Hence the achieved approximation ratio is .

Answer:

approxVertexCover returns (). Since are disjoint, an optimal cover is (), giving an achieved ratio of .

Subset Sum Problem and Its FPTAS (APPROX-SUBSET-SUM)

Given positive integers and target , the Subset Sum optimization problem finds a subset maximizing .

Example 3

3 (6 marks)

Trace APPROX-SUBSET-SUM with , target , and (so ). Compare the approximate answer against the exact optimum .

Steps and (using trim factor ):

  • Init: .
  • (): Merge . Trim (): .
  • (): Merge . Trim: keep ; keep ; since , trim ; keep . .

Steps and :

  • (): Merge . Trim ( trim ) and drop : .
  • (): Merge . Trim (, , ) and drop : .

Maximum returned sum , well within of the exact optimum (actual relative error ).

Answer:

APPROX-SUBSET-SUM returns (exact optimum is ; relative error ).


Exercises

Exercises — NP-Hard and NP-Complete Problems

Question 1

Define the complexity classes , , -Hard, and -Complete, and state Cook's Theorem along with its role in proving new problems -complete.

Definitions of complexity classes:

  • : Decision problems solvable in deterministic polynomial time.
  • : Decision problems verifiable in deterministic polynomial time (equivalently, solvable in non-deterministic polynomial time).
  • -Hard: Problems such that every reduces to in polynomial time ().
  • -Complete: Problems in that are also -hard.

Cook's Theorem and reduction proofs: Cook's Theorem proves directly from Turing machine encodings that SAT is -complete. Once SAT is established as -complete, proving any new problem only requires two steps: (1) show (give a polynomial-time verifier), and (2) reduce a known -complete problem to in polynomial time ().

Answer:

, and -Complete -Hard. Cook's Theorem proved SAT is -complete from first principles, enabling subsequent proofs via polynomial reductions .

Question 2

Show how reduces in polynomial time to (). Illustrate the reduction on a -vertex graph containing a -clique (with edges ), giving the corresponding vertex cover in .

Reduction construction (): Given , construct the complement graph where and , and ask whether has a vertex cover of size :

  • If is a -clique in , then no edge in has both endpoints in . Hence every edge in has at least one endpoint in , so is a vertex cover of of size .
  • If is a vertex cover of of size , then no edge of connects two vertices in , meaning every pair in is connected in —a -clique.

Illustration on the -vertex graph (): Edges of : , so is a -clique. Complement edges (all missing pairs): . Taking (size ): every edge in touches either or , confirming is a vertex cover of of size .

Answer:

has a -clique iff has a vertex cover of size . For the -vertex graph with -clique , the complement has vertex cover of size .

Question 3

Explain why code generation for expression DAGs on registers is -hard while tree code generation is linear-time, and list four pairs of NP-hard problems vs. their simplified polynomial-time counterparts.

Expression Trees vs. DAGs in Code Generation: In an expression tree, every intermediate value has a single parent use, so optimal evaluation order (minimizing register usage) is computed bottom-up in time via Sethi-Ullman labeling. In an expression DAG (caused by common subexpressions), a computed value may have multiple consumers; keeping its register occupied across distant subtrees can cause register spills, making optimal zero-spill ordering -hard.

Four NP-hard vs. simplified polynomial-time pairs:

  1. 3-SAT () vs. 2-SAT ( via SCCs).
  2. 3-Colorability () vs. 2-Colorability / Bipartiteness ( via BFS).
  3. Hamiltonian Cycle () vs. Eulerian Cycle ( via vertex degree parity).
  4. -Machine Flow Shop (-hard) vs. -Machine Flow Shop ( via Johnson's rule).
Answer:

Shared subexpressions in DAGs couple evaluation order with register lifetime, making -register code generation -hard (whereas expression trees take ). Key simplified tractable cases include 2-SAT, 2-Coloring, Eulerian Cycle, and 2-Machine Flow Shop.

Question 4

Distinguish between an -approximation algorithm, a PTAS, an FPTAS, and a probabilistically good algorithm, and prove that the edge-pair approxVertexCover algorithm always achieves an approximation ratio of at most .

Approximation scheme definitions:

  • -approximation: Returns within relative error : for a fixed .
  • PTAS: Parameterized by , runs in polynomial time in for any fixed (e.g. ).
  • FPTAS: Runs in time polynomial in both and (e.g. ).
  • Probabilistically good algorithm: A randomized polynomial-time algorithm that meets the target quality guarantee with high probability (e.g. ) on every input.

Proof of -approximation for Vertex Cover: Let be the set of edges selected by approxVertexCover (both endpoints of each are added to ). Since no chosen edge is picked after either endpoint is covered, the edges in are pairwise vertex-disjoint (a matching). Any optimal cover must contain at least one endpoint from each edge in , so . Since , it follows that .

Answer:

PTAS is polynomial in for fixed , FPTAS is polynomial in both and , and probabilistically good algorithms achieve high-probability guarantees via randomness. approxVertexCover chooses a matching with and , guaranteeing .

Question 5
  1. On a cycle graph with vertices and edges , trace approxVertexCover when edges are inspected in order and compute the ratio .
  2. Execute one trimming step of APPROX-SUBSET-SUM on the sorted list with , and list the trimmed result.

Tracing approxVertexCover on :

  • Edge is uncovered add to ().
  • Edge is covered (contains ).
  • Edge is uncovered add to ().
  • Edge is covered.

Thus . An optimal minimum vertex cover of is of size , so the achieved ratio is .

Trimming with :

  • Keep last = 0.
  • Check keep , set last = 50.
  • Check trim .
  • Check keep , set last = 100.
  • Check trim .

Trimmed list: .

Answer:
  1. On , approxVertexCover outputs () against , achieving ratio .
  2. Trimming with yields .
← Backtracking Techniques