Backtracking, branch and bound, and NP-completeness notes — Unit 5

When Greedy methods and Dynamic Programming both fail to find a solution, we must resort to exhaustive search (checking every single possible combination). However, a pure brute-force approach is often astronomically slow.

Backtracking is an intelligent, optimized brute-force technique.

⇒1.1 The Philosophy

Backtracking builds a solution incrementally, one piece at a time. It uses a State-Space Tree to represent all choices.

As it builds the solution, it constantly evaluates the current state against the problem constraints.
If the algorithm realizes that the current partial solution is invalid and can never lead to a correct final answer, it immediately stops exploring that branch. It "Backtracks" up the tree to the previous step and tries a different path.

This early abandonment of doomed paths is called Pruning. It saves massive amounts of computation time compared to naive brute-force.

The objective is to place $N$ chess queens on an $N \times N$ chessboard so that no two queens threaten each other. (No two queens can share the same row, column, or diagonal).

⇒2.1 The Backtracking Approach

We place queens one by one, column by column.

• 1. Start in the leftmost column.
• 2. Try placing a queen in the first row. Check if it's safe (no other queens to the left threaten it).
• 3. If safe, move to the next column and recursively try to place the next queen.
• 4. If we reach a column where the queen cannot be placed in ANY row, we hit a dead end. We backtrack: we return to the previous column, pick up the queen we placed there, and move it down to the next row.
• 5. If all $N$ queens are placed successfully, print the board.

Without backtracking, an $8 \times 8$ board has $64! / 56!$ possible placements. With backtracking pruning, the search space is reduced to a tiny fraction of that.

Given an undirected graph and $m$ colors, can you color every vertex such that no two adjacent vertices share the exact same color?

This is crucial for compiler register allocation and scheduling problems.

⇒3.1 The Backtracking Approach

• 1. Start with the first vertex. Try assigning Color 1.
• 2. Check constraints: Look at all adjacent vertices. If none are Color 1, it's safe.
• 3. Move to the next vertex. Try Color 1. If unsafe, try Color 2, then Color 3...
• 4. If you reach a vertex where ALL $m$ colors violate the adjacency constraint, you've hit a dead end. Backtrack to the previous vertex and change its color.
• 5. If all vertices are colored, a solution is found.

A Hamiltonian Cycle is a closed loop in an undirected graph that visits every single vertex exactly once and returns to the starting vertex.

⇒4.1 The Backtracking Approach

We build an array `path[]` to store the sequence of vertices.

• 1. Put vertex 0 into `path[0]`. This is our starting point.
• 2. To pick the next vertex `path[i]`, we iterate through all vertices. We check two constraints:
  a) Is there an actual edge between `path[i-1]` and this new vertex?
  b) Has this new vertex already been added to the path earlier? (To prevent visiting twice).
• 3. If safe, add it to the path and recurse.
• 4. If we get stuck, backtrack and try a different adjacent vertex.
• 5. When `path[]` is full (length $V$), check if there is an edge from the last vertex back to `path[0]`. If yes, we found a cycle.

Backtracking is generally used for finding any valid solution, or generating all valid solutions.
Branch and Bound (B&B) is a related technique designed exclusively for solving Optimization Problems (finding the absolute minimum cost solution).

⇒5.1 The Philosophy

Like Backtracking, B&B searches a state-space tree. However, instead of just checking for validity, it calculates a mathematical "Bound" (a best-case estimate) for every node in the tree.

Suppose we are trying to find a minimum cost path. We have already found one valid path that costs $500. This is our upper bound.

We start exploring a new branch of the tree. The current cost is $200. We calculate the optimistic lower bound for the remainder of this branch and find it is$400. Total estimated cost = $600. Because$600 is strictly worse than our known solution of $500, we immediately kill this branch. We don't explore it further. This is bounding.

The ultimate routing problem. Given a list of cities and the distances between each pair, what is the shortest possible route that visits each city exactly once and returns to the origin city?

This is a Minimum Hamiltonian Cycle problem. It is notoriously difficult. A brute force approach must check $(n-1)!$ permutations. For 20 cities, that's $1.2 \times 10^{17}$ routes.

⇒6.1 Branch and Bound Solution

To solve TSP efficiently using B&B, we must calculate a strong lower bound. We do this using Cost Matrix Reduction.

1. Subtract the minimum value of each row from all elements in that row. Add the subtrahend to a running total.
2. Do the same for columns.
3. The accumulated sum of these subtractions is the initial Lower Bound for the root node.

As we explore the tree (choosing to travel from City A to City B), we generate a new reduced matrix for that child node, calculate its new bound, and always choose to explore the child node with the lowest bound (Least Cost Search).

So far, we have studied algorithms that solve problems in polynomial time: $O(n)$, $O(n \log n)$, $O(n^2)$, $O(n^3)$. These are considered "efficient".

However, for some problems (like the Traveling Salesperson Problem, or breaking an RSA encryption key), decades of research by the brightest mathematicians on Earth have completely failed to produce a polynomial-time algorithm. The best known algorithms take exponential time: $O(2^n)$ or $O(n!)$.

Complexity theory is the study of classifying these mathematical problems based on their inherent difficulty.

Problems are grouped into mathematical sets (classes) based on how quickly a Turing Machine can solve them.

⇒8.1 Class P (Polynomial Time)

The set of all decision problems that can be solved by a deterministic computer in polynomial time.

These are the "easy" problems. Examples: Sorting an array, shortest path (Dijkstra), Matrix Multiplication.

⇒8.2 Class NP (Nondeterministic Polynomial Time)

The set of all decision problems where, if someone hands you a proposed solution, you can verify if that solution is correct in polynomial time.

Example: Sudoku. Solving a massive Sudoku puzzle from scratch is incredibly difficult. But if someone hands you a completed Sudoku board, you can verify if it's correct instantly (just check the rows and columns). Thus, Sudoku is in NP.

Crucially, any problem that can be solved quickly (P) can obviously be verified quickly. Therefore, $P$ is a subset of $NP$. ($P \subseteq NP$).

This leads to the most famous unsolved problem in theoretical computer science, carrying a $1,000,000 prize from the Clay Mathematics Institute.

⇒9.1 Does P = NP?

If a problem's solution can be verified quickly (NP), does that automatically mean there exists a hidden algorithm to solve it quickly (P), and we just haven't been smart enough to discover it yet?

• If $P = NP$, it means human creativity is automatable. We could find the cure for cancer in seconds. Current cryptography (which relies on the fact that factoring large primes is hard to solve but easy to verify) would completely collapse. The world would fundamentally change.
• Most computer scientists strongly believe $P \neq NP$. They believe some problems are inherently, fundamentally hard to solve, regardless of human ingenuity.

To understand the hardest problems in NP, we must understand the concept of Reduction.

⇒10.1 The Mechanism

Problem A is Polynomial-time Reducible to Problem B (denoted as $A \le_p B$) if we can write a fast (polynomial time) algorithm that transforms any instance of Problem A into an instance of Problem B.

Why is this important? If $A \le_p B$, it mathematically proves that Problem B is at least as hard as Problem A.

If we somehow discover a fast, magical algorithm to solve Problem B, we can use it to instantly solve Problem A as well (by transforming A into B, and running the B solver).

⇒11.1 Class NP-Hard

A problem is NP-Hard if EVERY SINGLE problem in the entire NP class can be polynomially reduced to it.
These are the absolute hardest problems in computer science. They are so hard that we aren't even sure if their solutions can be verified quickly (they are not necessarily in NP).

⇒11.2 Class NP-Complete

The overlap. A problem is NP-Complete if:
1. It is in NP (Solutions can be verified quickly).
AND
2. It is NP-Hard (Every other NP problem reduces to it).

The NP-Complete class contains the 'boss level' problems of computer science (TSP, Knapsack, Graph Coloring). They are all mathematically inter-linked. If anyone ever discovers a fast $O(n^2)$ algorithm for even ONE NP-Complete problem, it triggers a chain reaction: ALL NP-Complete problems instantly become solvable in polynomial time, proving $P = NP$.

How do you prove a problem is NP-Complete? You must prove that every single problem in NP reduces to it. But there are infinite problems in NP! This seemed impossible.

⇒12.1 The SAT Problem

Stephen Cook mathematically proved that the Boolean Satisfiability Problem (SAT) is NP-Complete. SAT asks: Given a complex boolean logic formula (e.g., $(A \lor B) \land (\neg A \lor C)$), is there an assignment of TRUE/FALSE to the variables that makes the entire formula evaluate to TRUE?

Cook achieved this by mapping the internal physical logic gates of a Turing Machine directly into a massive boolean formula.

Because of Cook's Theorem, we now have a starting point. To prove a new Problem X is NP-Complete, we don't need to reduce infinite problems to it. We just need to reduce SAT to Problem X. If SAT reduces to X, and SAT is the hardest problem, then X must also be the hardest problem.

Unit 5 covers the pinnacle of theoretical computer science.

⇒13.1 University Exam Checklist

• Explain the difference between Backtracking and Branch and Bound. Which one is used for optimization problems?
• Draw the state-space tree for the 4-Queens problem using Backtracking.
• Explain how Backtracking is applied to the Graph Coloring problem and the Hamiltonian Cycle problem.
• Describe how Branch and Bound uses lower bound calculations to prune the state-space tree for the Traveling Salesperson Problem (TSP).
• Define the complexity classes P and NP.
• What does it mean for a problem to be NP-Hard? NP-Complete?
• Explain the concept of Polynomial Reduction ($A \le_p B$).
• State Cook's Theorem and explain the significance of the Boolean Satisfiability (SAT) problem in complexity theory.
• Draw the Euler diagram showing the relationship between P, NP, NP-Complete, and NP-Hard (assuming $P \neq NP$).