NP-Completeness and Approximation Algorithms

The interview reality check

Now that we've covered Dynamic Programming, Greedy Algorithms, Graph Algorithms, Advanced Data Structures, and Bit Manipulation, you have a strong toolkit for solving many MAANG-style problems efficiently.

But some problems are different.

Sometimes an interviewer gives you a problem and the honest answer is not “use a clever data structure.” It is:

• The exact solution may be too slow for large inputs.
• The problem belongs to a class where no known polynomial-time algorithm exists.
• We should recognize the hardness, then choose a practical strategy.

That is where NP-completeness and approximation algorithms come in.

By the end, you should know how to say: “This looks computationally hard, so I’ll solve a restricted version, use exponential search for small n, or use an approximation.”

Three buckets to recognize

Think of algorithmic problems by how hard they are to solve and verify.

P

Problems we can solve in polynomial time, like:

• Binary search: O(log n)
• BFS/DFS: O(V + E)
• Dijkstra with a heap: roughly O(E log V)

These are the kinds of efficient solutions we practiced earlier.

NP

Problems where, if someone gives you a candidate answer, you can verify it in polynomial time.

Example: Subset Sum decision version

Given numbers and a target, is there some subset that sums to the target?

If someone hands you the subset, you can quickly add it up and check.

NP-complete

Problems that are both:

1. In NP
2. At least as hard as every problem in NP

If anyone finds a polynomial-time algorithm for one NP-complete problem, it would imply efficient solutions for all NP problems. That is the famous unsolved P vs NP question.

Optimization vs decision

NP-completeness is usually discussed using decision problems, where the answer is yes/no.

Many interview-style problems are optimization problems:

Find the minimum number of servers, edges, coins, routes, or groups.

To discuss hardness, we often convert them into decision form:

Is there a solution using at most k servers, edges, coins, routes, or groups?

This matters because decision versions are easier to compare through reductions.

Example

Optimization:

What is the minimum subset whose sum is exactly target?

Decision:

Does any subset sum to target?

Below is a small brute-force Java program for the decision version. It is correct, but it tries include/exclude choices, so it grows exponentially.

```java
public class Main {
    static boolean subsetSum(int[] nums, int i, int remaining) {
        if (remaining == 0) return true;
        if (i == nums.length || remaining < 0) return false;

        // Choice 1: include nums[i]
        boolean take = subsetSum(nums, i + 1, remaining - nums[i]);

        // Choice 2: skip nums[i]
        boolean skip = subsetSum(nums, i + 1, remaining);

        return take || skip;
    }

    public static void main(String[] args) {
        int[] nums = {3, 34, 4, 12, 5, 2};
        int target = 9;

        System.out.println("Subset sum exists? " + subsetSum(nums, 0, target));
        // Example subset: 4 + 5 = 9
    }
}
```

A problem is in NP if:

How problems prove hardness

A reduction converts one problem into another.

If problem A can be transformed into problem B, then a fast solver for B would also solve A.

Input for A  ->  transform  ->  Input for B
                         solve B
Answer for A <- convert back <- Answer for B

This is the core idea behind NP-completeness proofs.

Interview-level intuition

You usually do not need to prove NP-completeness from scratch in coding interviews.

But you should recognize signals like:

• “Try all subsets”
• “Try all orderings”
• “Minimum set of choices covering constraints”
• “Can we satisfy all constraints?”
• n is small, like n <= 20, suggesting exponential search may be acceptable

This connects directly to Recursion and Backtracking and Dynamic Programming: those tools still help, but they may not magically make every problem polynomial.

True or false?

If a problem is NP-complete, then no algorithm can ever solve it correctly.

When exact is too expensive

For some NP-hard optimization problems, we use approximation algorithms.

An approximation algorithm gives a solution that is:

• Fast enough to run on large inputs
• Not always optimal
• Mathematically bounded compared to optimal, when possible

Example guarantee

A 2-approximation means:

The algorithm's answer is at most 2 times worse than the optimal answer.

For minimization:

algorithmCost <= 2 * optimalCost

For maximization, the comparison is usually reversed:

algorithmValue >= optimalValue / 2

This is different from the greedy lesson. A greedy algorithm is a strategy. An approximation algorithm is a strategy plus a quality guarantee.

A classic approximation

A vertex cover in a graph is a set of vertices that touches every edge.

Problem:

Find the smallest vertex cover.

The exact minimum vertex cover problem is NP-hard for general graphs.

But there is a simple 2-approximation:

1. Pick any uncovered edge (u, v).
2. Add both u and v to the cover.
3. Remove all edges touching u or v.
4. Repeat.

Why the factor 2 intuition works:

• Every picked edge must be covered by any valid solution.
• The picked edges do not share endpoints after removal.
• Optimal needs at least one endpoint per picked edge.
• We take two endpoints per picked edge.

So our cover is at most twice the optimal size.

```java
import java.util.*;

public class Main {
    static class Edge {
        int u, v;
        Edge(int u, int v) { this.u = u; this.v = v; }
        public String toString() { return "(" + u + "," + v + ")"; }
    }

    static Set<Integer> approximateVertexCover(List<Edge> edges) {
        Set<Integer> cover = new LinkedHashSet<>();
        boolean[] removed = new boolean[edges.size()];

        for (int i = 0; i < edges.size(); i++) {
            if (removed[i]) continue;

            Edge chosen = edges.get(i);
            cover.add(chosen.u);
            cover.add(chosen.v);

            for (int j = 0; j < edges.size(); j++) {
                Edge e = edges.get(j);
                if (e.u == chosen.u || e.v == chosen.u ||
                    e.u == chosen.v || e.v == chosen.v) {
                    removed[j] = true;
                }
            }
        }
        return cover;
    }

    public static void main(String[] args) {
        List<Edge> edges = Arrays.asList(
            new Edge(0, 1), new Edge(1, 2), new Edge(2, 3),
            new Edge(3, 4), new Edge(4, 5), new Edge(1, 5)
        );

        Set<Integer> cover = approximateVertexCover(edges);
        System.out.println("Approx vertex cover: " + cover);
        System.out.println("Cover size: " + cover.size());
    }
}
```

Fill in the blank:

If an approximation algorithm for a minimization problem guarantees algorithmCost <= 2 * optimalCost, we call it a ___-approximation.

Fill in the blank: _____________

Another practical pattern

Set Cover is another famous NP-hard problem.

You have:

• A universe of items to cover
• Several sets, each covering some items
• Goal: choose as few sets as possible to cover everything

This appears in real systems as test selection, feature coverage, monitoring, ad placement, and resource planning.

A common approximation-style heuristic is:

Repeatedly pick the set that covers the largest number of currently uncovered items.

This greedy choice is not always optimal, but it is useful and has known approximation guarantees in theory.

Here is a small Java version.

```java
import java.util.*;

public class Main {
    static List<String> greedySetCover(Set<String> universe, Map<String, Set<String>> sets) {
        Set<String> uncovered = new HashSet<>(universe);
        List<String> chosen = new ArrayList<>();

        while (!uncovered.isEmpty()) {
            String bestName = null;
            int bestGain = 0;

            for (Map.Entry<String, Set<String>> entry : sets.entrySet()) {
                int gain = 0;
                for (String item : entry.getValue()) {
                    if (uncovered.contains(item)) gain++;
                }

                if (gain > bestGain) {
                    bestGain = gain;
                    bestName = entry.getKey();
                }
            }

            if (bestName == null) {
                throw new IllegalStateException("Some items cannot be covered");
            }

            chosen.add(bestName);
            uncovered.removeAll(sets.get(bestName));
        }

        return chosen;
    }

    public static void main(String[] args) {
        Set<String> universe = new HashSet<>(Arrays.asList(
            "arrays", "graphs", "dp", "greedy", "strings", "bits"
        ));

        Map<String, Set<String>> sets = new LinkedHashMap<>();
        sets.put("Plan A", new HashSet<>(Arrays.asList("arrays", "graphs", "dp")));
        sets.put("Plan B", new HashSet<>(Arrays.asList("greedy", "strings")));
        sets.put("Plan C", new HashSet<>(Arrays.asList("graphs", "bits")));
        sets.put("Plan D", new HashSet<>(Arrays.asList("bits", "strings", "greedy")));

        System.out.println("Chosen sets: " + greedySetCover(universe, sets));
    }
}
```

What to say in interviews

When a problem starts looking NP-hard, do not panic. Use a structured response.

1. Clarify constraints

Ask about input size.

• n <= 20: backtracking or bitmask DP may be fine.
• n <= 10^5: exact exponential search is probably impossible.

2. Identify the shape

Look for:

• Subsets
• Permutations
• Constraint satisfaction
• Minimum cover
• Scheduling with many interacting constraints

3. Offer levels of solution

A strong answer might sound like:

“The exact version appears exponential. For small inputs I can use backtracking with pruning. For larger inputs, I would use a greedy approximation and explain its tradeoff.”

4. Connect to your toolkit

Use what you already learned:

• Backtracking for exhaustive search
• DP for overlapping subproblems or bitmask states
• Greedy when you can prove optimality or provide an approximation guarantee
• Graphs and Hashing to model and speed up checks

Next, we will briefly zoom out from algorithms into how larger systems are designed.