ADVANCED ALGORITHMS - NP-COMPLETENESS:Landscape of NP-Complete Problems

Landscape of NP-Complete Problems

The Reduction Web

NP-complete problems form an interconnected web. Every NP-complete problem reduces to every other. The canonical starting point is 3-SAT:

3-SAT
  ├─ Independent Set
  │    ├─ Vertex Cover
  │    └─ Clique
  ├─ Hamiltonian Cycle
  │    ├─ Hamiltonian Path
  │    └─ Travelling Salesman (decision)
  └─ 3-Colorability
       └─ k-Colorability (k ≥ 3)

Subset Sum ──► Partition ──► Bin Packing ──► Knapsack

Classic NP-Complete Problems

1. Vertex Cover

Problem: Given graph G and integer k, does G have a vertex cover of size ≤ k?

(A vertex cover is a set of vertices such that every edge has at least one endpoint in the set.)

Greedy 2-approximation (best known polynomial-time ratio for VC):

def approx_vertex_cover(graph):
    """2-approximation: pick both endpoints of each uncovered edge."""
    covered = set()
    cover = set()
    for u, v in graph.edges():
        if u not in covered and v not in covered:
            cover.add(u)
            cover.add(v)
            covered.add(u)
            covered.add(v)
    return cover  # At most 2× optimal

2. Independent Set

Problem: Given G and k, does G have an independent set of size ≥ k?

(No two vertices in the set are adjacent.)

Relation: |maximum independent set| + |minimum vertex cover| = |V| (König's theorem for bipartite graphs; not true in general).

3. Clique

Problem: Given G and k, does G have a clique of size ≥ k?

(A clique is a complete subgraph — every pair of vertices connected.)

Reduction from IS: G has an IS of size k ↔ complement(G) has a clique of size k.

4. 3-Colorability

Problem: Can the vertices of G be colored with 3 colors such that no two adjacent vertices share a color?

Real application: Register allocation — program variables are graph nodes, edges mean "live at same time", colors are CPU registers.

def is_3_colorable(graph):
    """Brute force check — exponential, for illustration only."""
    n = len(graph)
    for coloring in itertools.product([0, 1, 2], repeat=n):
        valid = True
        for u, v in graph.edges():
            if coloring[u] == coloring[v]:
                valid = False
                break
        if valid:
            return True, list(coloring)
    return False, None

5. Subset Sum

Problem: Given integers a₁, …, aₙ and target t, does any subset sum to exactly t?

Pseudo-polynomial DP (polynomial in n and t, but t can be exponential in the input size):

def subset_sum(nums, target):
    """O(n * target) — pseudo-polynomial, NOT polynomial in input size."""
    dp = {0}
    for num in nums:
        dp = dp | {s + num for s in dp}
    return target in dp

6. Travelling Salesman Problem (Decision)

Problem: Given weighted complete graph and bound B, is there a tour of cost ≤ B visiting every city exactly once?

Euclidean TSP (cities are points in the plane) has a PTAS (polynomial-time approximation scheme), but the general metric TSP has no better-than-1.5-approximation unless P = NP (Christofides gives 1.5-approx).

7. Set Cover

Problem: Given universe U, sets S₁, …, Sₘ ⊆ U, and integer k, can we cover U with ≤ k sets?

Greedy O(log n)-approximation (optimal for polynomial-time algorithms unless P = NP):

def greedy_set_cover(universe, sets):
    """Logarithmic approximation: always pick the set covering the most uncovered elements."""
    covered = set()
    cover = []
    while covered != universe:
        best = max(sets, key=lambda s: len(s - covered))
        cover.append(best)
        covered |= best
    return cover

8. Hamiltonian Cycle

Problem: Does G contain a cycle that visits every vertex exactly once?

Note: Eulerian cycle (visits every edge once) is solvable in O(E) — the two problems look similar but have vastly different complexity!

How to Identify NP-Hard Problems in Practice

A problem is likely NP-hard if:

1. It asks for an optimal subset/assignment from an exponential search space
2. Small changes to the problem statement make it polynomial (e.g., 2-SAT vs 3-SAT, shortest path vs longest path)
3. It generalizes a known NP-hard problem
4. No polynomial-time algorithm has been found despite decades of research

Warning signs in code challenges:

• "Find the minimum/maximum set/partition such that..."
• "Does there exist a configuration satisfying all constraints..."
• Input size grows but runtime required is polynomial (impossible for NP-hard unless P = NP)

The Coping Toolkit

When you encounter NP-hard problems in practice:

1. Approximation algorithms: Get solution within known ratio of optimal
2. Parameterized algorithms: Poly-time if some parameter is small (FPT algorithms)
3. Special structure: Exploit planarity, tree-width, bipartiteness for exact poly-time algorithms
4. Heuristics: Genetic algorithms, simulated annealing, local search
5. SAT solvers: Modern CDCL solvers handle surprisingly large instances

Practice Problems

1. Prove that Clique is NP-complete (reduce from Independent Set)
2. Show that 3-Colorability ≤ₚ SAT
3. Implement the greedy set cover and verify it achieves H(n) approximation ratio
4. Given a graph, determine in polynomial time whether it is 2-colorable (bipartite check)
5. Explain why Subset Sum is NP-hard even though its DP solution is "fast" for small values of t