Hard Problems and Heuristics

Classic NP-Hard Problems and Heuristic Methods

Three canonical NP-Hard optimisation problems illustrate the need for heuristic approaches when exact solutions are computationally intractable.

Graph Colouring Problem

Problem: Assign colours to the vertices of a graph so that no two adjacent vertices share the same colour, using the minimum number of colours (the chromatic number $\chi(G)$).

Applications: Exam scheduling (vertices = exams, edges = shared students), register allocation in compilers, frequency assignment in wireless networks.

Complexity: Finding $\chi(G)$ is NP-Hard. Deciding whether a graph is 3-colourable is NP-Complete.

Greedy Heuristic

function GreedyColour(G):
    sort vertices by degree (largest first)
    for each vertex v in order:
        assign the smallest colour not used by any neighbour of v
    return colouring

Runs in $O(V + E)$ but does not guarantee the minimum number of colours.

KEY TAKEAWAY: The greedy colouring heuristic is fast but may use more colours than the chromatic number. The order in which vertices are processed affects solution quality.

0-1 Knapsack Problem

Problem: Given $n$ items each with weight $w_i$ and value $v_i$, and a knapsack of capacity $W$, choose a subset of items to maximise total value without exceeding capacity. Each item is either included (1) or excluded (0).

$$\text{maximise} \sum_{i} v_i x_i \quad \text{subject to} \sum_{i} w_i x_i \leq W, \quad x_i \in {0, 1}$$

Complexity: $2^n$ possible subsets. NP-Hard in general.

Greedy Heuristic (Value-to-Weight Ratio)

function GreedyKnapsack(items, W):
    sort items by v_i / w_i descending
    total_weight = 0; total_value = 0
    for each item in sorted order:
        if total_weight + w_i <= W:
            include item
            total_weight += w_i
            total_value += v_i
    return total_value

This greedy approach does not guarantee the optimal solution for the 0-1 variant (it is optimal for the fractional variant).

EXAM TIP: Know the difference: in the fractional knapsack, the greedy value/weight ratio strategy is optimal; in the 0-1 knapsack, it is a heuristic only.

Travelling Salesman Problem (TSP)

Problem: Given a complete weighted graph, find the shortest Hamiltonian cycle (visit every vertex exactly once and return to the start).

Applications: Delivery routing, circuit board drilling, supply chain optimisation.

Complexity: $\frac{(n-1)!}{2}$ distinct tours for $n$ cities. NP-Hard; no known polynomial algorithm.

Nearest-Neighbour Heuristic

function NearestNeighbour(G, start):
    tour = [start]; visited = {start}; current = start
    while not all vertices visited:
        next = nearest unvisited vertex to current
        tour.append(next); visited.add(next); current = next
    tour.append(start)
    return tour

Runs in $O(V^2)$. Typically produces tours 20-25% longer than optimal.

Other TSP Heuristics

COMMON MISTAKE: Heuristics for TSP do not guarantee the optimal tour. They trade optimality for tractability. Always state this limitation.

Summary

VCAA FOCUS: Understand why these problems are computationally intractable, describe at least one heuristic for each, and explain the trade-off between solution quality and computational cost. Heuristics overcome the soft limits of computation.