The Algorithm Design Manual Second Edition

9.3

Elementary Hardness Reductions

The reductions in the previous section demonstrate transformations between pairs

of problems for which efficient algorithms exist. However, we are mainly concerned

with using reductions to prove hardness, by showing that a fast algorithm for

Bandersnatch would imply one that cannot exist for Bo-billy.

---

324

9 .

I N T R A C T A B L E P R O B L E M S A N D A P P R O X I M A T I O N A L G O R I T H M S

Figure 9.3: Graphs with (l) and without (r) Hamiltonian cycles

For now, I want you to trust me when I say that Hamiltonian cycle and vertex

cover are hard problems. The entire picture (presented in Figure

9.2

) will become

clear by the end of the chapter.