How do I construct reductions between problems to prove a problem is NP-complete?

Question

I am taking a complexity course and I am having trouble with coming up with reductions between NPC problems. How can I find reductions between problems? Is there a general trick that I can use? How should I approach a problem that asks me to prove a problem is NPC?

Answer 1

There is no magic bullet; NP-hardness proofs are hard. However, there is a general framework for all such proofs. Many students who struggle with NP-hardness proofs are confused about what they're supposed to be doing, which obviously makes it impossible to figure out how to do it. So here is what to do to prove a problem NP-hard.

First, unless you're just doing homework, you have to decide which NP-hard problem to reduce to your problem. This is largely a question of "smell". If the number 3 appears anywhere in the problem statement, try reducing from $\mathsf{3SAT}$ or $\mathsf{3Color}$ or $\mathsf{3Partition}$. (Yes, I'm serious.) If your problem involves finding an optimal subsequence or permutation or path, try reducing from $\mathsf{HamiltonianCycle}$ or $\mathsf{HamiltonianPath}$. If your problem asks for the smallest subset with a certain property, try $\mathsf{Clique}$; if it asks for the largest subset with a certain property, try $\mathsf{IndependentSet}$. If your problem involves doing something in the plane, try $\mathsf{PlanarCircuitSAT}$ or $\mathsf{PlanarTSP}$. And so on. If your problem doesn't "smell" like anything, $\mathsf{3SAT}$ or $\mathsf{CircuitSAT}$ is probably your best bet.

Obviously, you need to already know precisely how all these problems are defined, and the simpler the problem you reduce from, the better. So as cool as the result might look in the end, I don't recommend reducing from $\mathsf{Minesweeper}$ or $\mathsf{Tetris}$ or $\mathsf{OneCheckersMove}$ or $\mathsf{SuperMarioBros}$.

Second, the actual reduction. To reduce problem X (the one you know is NP-hard) to problem Y (the one you're trying to prove is NP-hard, you need to describe an algorithm that transforms an arbitrary instance of X into a legal instance of Y. The reduction algorithm needs to do something specific with each "feature" of the X-instance; the portion of the output for each "feature" is usually called a gadget.

But what's a feature? That depends on problem X. For example:

• To transform an instance of $\mathsf{3SAT}$, you'll need a gadget for each variable and for each clause in the input formula. Each variable gadget should have two "states" that correspond to "true" and "false". Each clause gadget should also have multiple "states", each of which somehow forces at least one of the literals in that clause to be true. (The states are not part of the output of the reduction algorithm.)

• To transform an instance of $\mathsf{3Color}$, you'll need a gadget for each vertex and each edge of the input graph, and another gadget to define the three colors.

• To transform an instance of $\mathsf{PlanarCircuitSat}$, you'll need a gadget for each input, for each wire, and for each gate in the input circuit.

The actual form of the gadget depends on problem Y, the one you're reducing to. For example, if you're reducing to a problem about graphs, your gadgets will be small subgraphs; see the Wikipedia article. If you're reducing to a problem about scheduling, each gadget will be a set of jobs to be scheduled. If you're reducing to a problem about Mario, each gadget will be a set of blocks and bricks and Koopas.

This can get confusing if both problems involve the same kind of object. For example, if both X and Y are problems about graphs, your algorithm is going to transform one graph (an instance of X) into a different graph (an instance of Y). Choose your notation wisely, so that you don't confuse these two graphs. I also strongly recommend using multiple colors of ink.

Finally, your reduction algorithm must satisfy three properties:

• It runs in polynomial time. (This is usually easy.)

• If your reduction algorithm is given a positive instance of X as input, it produces a positive instance of Y as output.

• If your reduction algorithm produces a positive instance of Y as output, it must have been given a positive instance of X as input.

There's an important subtlety here. Your reduction algorithm only works in one direction, from instances of X to instances of Y, but proving the algorithm correct requires reasoning about the transformation in both directions. You must also remember that your reduction algorithm cannot tell whether a given instance of X is positive or negative—that would require solving an NP-hard problem in polynomial time!

That's the what. The how just comes with practice.

Answer 2

JeffE outlines the most common strategy: know lots of NP-complete problems, find one that fits very well and make the easy reduction.

Another valid strategy is to always use 3SAT (or any other problem). This might make some reductions more intricate, but the upside is that you have lots of experience expressing satifiability in other types of problems. So you save the time of finding a good reduction partner (including dead-ends) and hope that your experience will allow you to do the reduction quickly even if it is harder.

This approach has some meta beauty, too: (3)SAT is one of the few problems for which NP-completeness has been proven (almost) directly. Therefore, relying only on that proof keeps your "proof tree" flat, avoiding long chains of reductions.