Unit 6: Backtracking, Approximation, and Complexity Classes

I. Algorithmic Strategies and Computational Complexity

This unit connects exact search methods, efficient approximation methods, and complexity theory. Backtracking and branch and bound explore combinatorial solution spaces; approximation algorithms trade optimality for polynomial running time; complexity classes classify problems by the resources required to solve or verify them.

• Search space: A problem is represented as states or partial solutions connected by choices, often forming a state-space tree.
• Feasibility and optimality:
  • A feasibility problem asks whether any solution satisfies the constraints.
  • An optimization problem seeks a feasible solution minimizing or maximizing an objective function.
• Backtracking principle: Abandon a partial solution as soon as it violates a constraint.
• Branch-and-bound principle: Abandon a feasible or partial branch when its bound proves that it cannot improve the current best solution.
• Approximation principle: Produce a polynomial-time solution with a provable relationship to the optimum.
• Complexity convention: Input size is measured by the number of bits needed to encode an instance; polynomial time means (O(n^k)) for a constant (k).

II. Backtracking Search — Constraint-Driven Enumeration

A. n-Queens Problem

The n-Queens problem places (n) queens on an (n \times n) chessboard so that no two attack each other.

• Constraints: Exactly one queen is placed in each row; queens in rows (i) and (j) must satisfy:
  
  TEXT

    column[i] ≠ column[j]
    |column[i] - column[j]| ≠ |i - j|

  
  Here, column[i] is the column occupied by the queen in row (i).
• Backtracking: Place a queen row by row and reject any column attacked by an earlier queen.
• Pseudocode:
  
  TEXT

    Place(row):
        if row > n: report solution
        for col = 1 to n:
            if Safe(row, col):
                column[row] = col
                Place(row + 1)

• Complexity: The unrestricted board has (n^n) row-wise assignments; unique-column pruning reduces the search toward (O(n!)), though actual exploration depends on pruning.
• Concrete case: For (n=4), one solution is ([2,4,1,3]), meaning queens occupy ((1,2),(2,4),(3,1),(4,3)).

III. Graph Search — Visiting Every Vertex Once

A. Hamiltonian Circuit

A Hamiltonian circuit is a cycle that visits every vertex of a graph exactly once and returns to the starting vertex.

• Representation: For graph (G=(V,E)), maintain a path (x_1,x_2,\ldots,x_n), where (x_1) is fixed to avoid rotational duplicates.
• Feasibility conditions:
  • ((xi,x{i+1})\in E) for (1\leq i<n).
  • All (x_i) are distinct.
  • ((x_n,x_1)\in E).
• Backtracking step: Add an unvisited vertex adjacent to the last path vertex; backtrack if no such vertex exists.
• Cost: Testing permutations gives worst-case time (O(n!)); an adjacency matrix supports (O(1)) edge checks.
• Distinction: A Hamiltonian circuit concerns vertices, whereas an Euler circuit uses every edge exactly once.

IV. Combinatorial Selection — Exact Target Construction

A. Subset-Sum Problem

The subset-sum problem asks whether a subset of integers has sum exactly equal to a target (T).

• Decision model: Given (a_1,\ldots,a_n), choose (x_i\in{0,1}) such that:
  
  TEXT

    Σ(a_i x_i) = T

• Backtracking choices: At item (a_i), either include it or exclude it, producing a binary state-space tree with at most (2^n) leaves.
• Pruning for positive inputs: Stop when the partial sum exceeds (T), or when adding all remaining values still cannot reach (T).
• Dynamic programming: For nonnegative integers, reachable sums can be computed in (O(nT)) time and (O(T)) space; this is pseudo-polynomial because (T) may be exponential in its bit length.
• Complexity status: The decision version is NP-complete.

V. Optimization Search — Bounds over the State-Space Tree

A. Branch and Bound

Branch and bound is an exact optimization framework that partitions the solution space and prunes subproblems using objective bounds.

• Branching: Divide a problem into smaller cases, such as “include item (i)” and “exclude item (i).”
• Bounding: For minimization, a node’s lower bound estimates the least possible cost below it; prune when:
  
  TEXT

    lower_bound(node) ≥ incumbent_cost

• Incumbent: The best complete feasible solution found so far supplies the pruning threshold.
• Node selection:
  1. FIFO: Breadth-first exploration.
  2. LIFO: Depth-first exploration with low memory.
  3. Least-cost: Expand the node with the most promising bound.
• Limitation: It remains exponential in the worst case, but strong bounds can eliminate most nodes.

VI. Minimum-Cost Matching

A. Assignment Problem

The assignment problem matches (n) agents to (n) jobs, assigning each exactly once while minimizing total cost.

• Mathematical model:
  
  TEXT

    Minimize Σ_i Σ_j c_ij x_ij
    subject to Σ_j x_ij = 1
               Σ_i x_ij = 1
               x_ij ∈ {0,1}

  
  Here, (c_{ij}) is the cost of assigning agent (i) to job (j).
• Branch and bound: A tree level assigns one agent; a lower bound combines fixed costs with optimistic minimum costs for unassigned agents.
• Efficient exact method: The Hungarian algorithm solves the standard assignment problem in (O(n^3)) time.
• Interpretation: It is a minimum-weight perfect matching problem in a bipartite graph.

VII. Capacity-Constrained Selection

A. Knapsack Problem

The 0/1 knapsack problem selects indivisible items to maximize profit without exceeding capacity (W).

• Model:
  
  TEXT

    Maximize Σ p_i x_i
    subject to Σ w_i x_i ≤ W
               x_i ∈ {0,1}

  
  Here, (p_i) and (w_i) are item profit and weight.
• Branch-and-bound bound: Sort by (p_i/w_i) and fill remaining capacity fractionally; the fractional-knapsack value is an upper bound on any 0/1 solution.
• Dynamic programming: Integer capacities permit (O(nW)) time, which is pseudo-polynomial.
• Variant distinction: Fractional knapsack is greedily solvable; 0/1 knapsack is NP-hard, and its decision version is NP-complete.

VIII. Minimum-Cost Tours

A. Traveling Salesman Problem

The Traveling Salesman Problem seeks a minimum-cost tour visiting every city exactly once and returning to the start.

• Graph model: In a weighted graph, minimize:
  
  TEXT

    c(x_n,x_1) + Σ from i=1 to n-1 of c(x_i,x_(i+1))

• Branching: Construct a tour city by city or include/exclude candidate edges.
• Lower bounds: Common bounds use reduced cost matrices, minimum incident edges, or minimum spanning trees.
• Complexity: Brute-force enumeration requires ((n-1)!/2) undirected tours; the decision version is NP-complete.
• Metric case: If edge costs satisfy the triangle inequality, shortcutting repeated vertices does not increase tour cost, enabling approximation guarantees.

IX. Near-Optimal Polynomial-Time Methods

A. Approximation Algorithms

An approximation algorithm efficiently returns a feasible solution whose quality is provably close to optimal.

• Approximation ratio: For cost (C) and optimum (OPT), a minimization algorithm has ratio (\rho) when:
  
  TEXT

    C ≤ ρ · OPT

  
  For maximization, the usual guarantee is (C \geq OPT/\rho).
• Absolute versus asymptotic: An asymptotic ratio permits an additive constant, such as (C\leq \rho OPT+k).
• Schemes:
  • PTAS: For every fixed (\varepsilon>0), achieves ratio (1+\varepsilon) in polynomial time.
  • FPTAS: Also runs polynomially in (1/\varepsilon).
• Role: Approximation is especially useful for NP-hard optimization problems when exact exponential search is impractical.

X. Covering Graph Edges

A. Vertex-Cover

A vertex cover is a set (C\subseteq V) such that every edge has at least one endpoint in (C).

• Optimization goal: Minimize (|C|); the decision version asks whether a cover of size at most (k) exists.
• 2-approximation: Repeatedly select an uncovered edge ((u,v)), add both endpoints to (C), and remove all incident edges.
• Guarantee: Selected edges form a matching (M). Any vertex cover needs at least one endpoint of each edge in (M), so:
  
  TEXT

    OPT ≥ |M| and |C| = 2|M| ≤ 2OPT

• Complexity: The decision problem is NP-complete, while the approximation runs in polynomial time.

XI. Covering a Universe of Elements

A. Set-Covering

Set covering selects the fewest subsets whose union equals a required universe (U).

• Input: A family (S_1,\ldots,Sm\subseteq U); choose indices (I) such that (\bigcup{i\in I}S_i=U).
• Greedy rule: Repeatedly choose the set covering the largest number of currently uncovered elements.
• Weighted version: Select the set minimizing cost per newly covered element:
  
  TEXT

    cost(S) / |S ∩ uncovered|

• Guarantee: Greedy set cover achieves approximation factor (H_{|U|}\leq 1+\ln |U|), where (Hn=\sum{i=1}^{n}1/i).
• Complexity: Minimum set cover is NP-hard; its decision version is NP-complete.

XII. Packing under Capacity Limits

A. Bin Packing Problems

Bin packing places items of sizes (0<s_i\leq 1) into the minimum number of unit-capacity bins.

• Constraint: For every bin (B), (\sum_{i\in B}s_i\leq 1).
• Common heuristics:
  1. First Fit: Place each item in the first bin with enough remaining capacity.
  2. Best Fit: Use the feasible bin leaving the least unused space.
  3. First Fit Decreasing: Sort items in decreasing size, then apply First Fit.
• Performance: First Fit Decreasing has asymptotic approximation ratio (11/9).
• Lower bound: Every solution needs at least (\left\lceil\sum_i s_i\right\rceil) bins.
• Complexity: Optimization bin packing is NP-hard.

XIII. Resource-Based Classification

A. Complexity Classes

Complexity classes group computational problems according to resource bounds and computational models.

• Decision problems: Complexity theory normally studies yes/no languages; optimization problems are related through decision forms.
• Polynomial reductions: (A\leq_p B) means instances of (A) can be transformed into equivalent instances of (B) in polynomial time.
• Importance: If (A\leq_p B) and (B) has a polynomial-time algorithm, then (A) also has one.
• Resources: Major measures include deterministic time, nondeterministic time, and memory space.

XIV. Efficient Deterministic Solvability

A. P

P is the class of decision problems solvable by a deterministic algorithm in polynomial time.

• Formal form: A problem belongs to P if some algorithm solves inputs of length (n) in (O(n^k)) time for a constant (k).
• Examples: Graph connectivity, shortest paths with nonnegative weights, minimum spanning tree, and assignment are in P.
• Interpretation: P is commonly treated as the class of efficiently solvable decision problems.
• Closure: P is closed under complement, union, intersection, and polynomial-time composition.

XV. Efficient Verification

A. NP

NP is the class of decision problems whose yes-instances possess polynomial-size certificates verifiable in polynomial time.

• Verifier model: Problem (L) is in NP if:
  
  TEXT

    x ∈ L iff there exists certificate y
    such that V(x,y) accepts in polynomial time

• Example: A Hamiltonian circuit is certified by a vertex sequence; adjacency and uniqueness can be checked polynomially.
• Relationship: (P\subseteq NP), because a polynomial-time solver can verify an answer without requiring a separate certificate.
• Open question: Whether (P=NP) remains unresolved.

XVI. At Least as Hard as Every NP Problem

A. NP-Hard

A problem is NP-hard if every problem in NP can be polynomially reduced to it.

• Definition: (H) is NP-hard when, for every (L\in NP), (L\leq_p H).
• Membership: An NP-hard problem need not belong to NP; it may be an optimization problem or even an undecidable problem.
• Proof method: Reduce a known NP-hard problem to the candidate problem, preserving yes/no answers and using polynomial time.
• Examples: Optimization versions of TSP, knapsack, set cover, and bin packing are NP-hard.

XVII. Hardest Decision Problems within NP

A. NP-Complete Problems

A problem is NP-complete precisely when it is both in NP and NP-hard.

• Two-part proof:
  1. Show that proposed certificates can be verified in polynomial time.
  2. Give a polynomial-time reduction from a known NP-complete problem.
• Foundational result: Boolean satisfiability, SAT, was the first problem proved NP-complete through the Cook–Levin theorem.
• Examples: Hamiltonian Circuit, Subset-Sum, Vertex-Cover, Set-Cover decision, and TSP decision are NP-complete.
• Consequence: If any NP-complete problem is solved in polynomial time, then every NP problem is polynomial-time solvable and (P=NP).