The Algorithm Design Manual Second Edition

9.5

Creative Reductions

Since both satisfiability and 3-SAT are known to be hard, we can use either of

them in reductions. Usually 3-SAT is the better choice, because it is simpler to

work with. What follows are a pair of more complicated reductions, designed to

serve as examples and also increase our repertoire of known hard problems. Many

---

9 . 5

C R E A T I V E R E D U C T I O N S

331

reductions are quite intricate, because we are essentially programming one problem

in the language of a significantly different problem.

One perpetual point of confusion is getting the direction of the reduction right.

Recall that we must transform every instance of a known NP-complete problem

into an instance of the problem we are interested in. If we perform the reduction

the other way, all we get is a slow way to solve the problem of interest, by using

a subroutine that takes exponential time. This always is confusing at first, for this

direction of reduction seems backwards. Make sure you understand the direction

of reduction now, and think back to this whenever you get confused.