The Algorithm Design Manual Second Edition

9.1.2

Decision Problems

Reductions translate between problems so that their answers are identical in every

problem instance. Problems differ in the range or type of possible answers. The

traveling salesman problem returns a permutation of vertices as the answer, while

other types of problems return numbers as answers, perhaps restricted to positive

numbers or integers.

The simplest interesting class of problems have answers restricted to true and

false. These are called decision problems. It proves convenient to reduce/translate

answers between decision problems because both only allow true and false as pos-

sible answers.

Fortunately, most interesting optimization problems can be phrased as decision

problems that capture the essence of the computation. For example, the traveling

salesman decision problem could be defined as:

---

9 . 2

R E D U C T I O N S F O R A L G O R I T H M S

319

Problem: The Traveling Salesman Decision Problem

Input: A weighted graph G and integer k.

Output: Does there exist a TSP tour with cost

≤ k?

The decision version captures the heart of the traveling salesman problem, in

that if you had a fast algorithm for the decision problem, you could use it to do a

binary search with different values of k and quickly hone in on the optimal solution.

With a little more cleverness, you could reconstruct the actual tour permutation

using a fast solution to the decision problem.

From now on we will generally talk about decision problems, because it proves

easier and still captures the power of the theory.