3.1 What is an Algorithm?

Consider a computational problem on graphs, such as the planarity testing problem: given a graph, is it planar? If a given graph is small, one may perform the test by hand. However the problem would not be solved without the help of fast computers if a given graph has hundreds or thousands of vertices. Thus we need an algorithm : a precise method usable by a computer to solve a problem. An algorithm must solve any instances of a problem and terminate after a finite number of operations.

Direct application of Kuratowski s theorem (Theorem 2.2.1) provides the following procedure for the planarity testing problem:

Systematically generate all (edge-induced) subgraph J of a given graph G, and check whether each of the J s is a subdivision of K ₅ or K _3,3. If there is at least one such J, G is nonplanar; otherwise G is planar.

Clearly a graph G of m edges has 2 ^m subgraphs, and it is easy to check whether each of them is a subdivision of K ₅ or K _3,3. Thus the procedure above can test the planarity for any given graph and terminate within finite time. That is, it is indeed an algorithm, although it is not efficient.

Let us consider the following classical question: is there a computational problem for which there is no algorithm? A.M.Turing [Tur36] introduced a mathematical model of computers, called a