The Design of Efficient Algorithms

Martin Charles Golumbic

1 The Complexity of Computer Algorithms

With the advent of the high-speed electronic computer, new branches of applied mathematics have sprouted forth. One area that has enjoyed a most rapid growth in the past decade is the complexity analysis of computer algorithms. At one level, we may wish to compare the relative efficiencies of procedures which solve the same problem. At a second level, we can ask whether one problem is intrinsically harder to solve than another problem. It may even turn out that a task is too hard for a computer to solve within a reasonable amount of time. Measuring the costs to be incurred by implementing various algorithms is a vital necessity in computer science, but it can be a formidable challenge.

Let us reflect for a moment on the differences between computability and computational complexity. These two topics, along with formal languages, become the pillars of the theory of computation. Computability addresses itself mostly to questions of existence: Is there an algorithm which solves problem Π? An early surprise for many math and computer science students is that one can prove mathematically that computers cannot do everything. A standard example is the unsolvability of the halting problem. Loosely stated, this says that it is impossible for a professor to write a computer program which will accept as data any student’s programming assignment and will return either the answer “yes, this student’s program will halt within finite time” or “no, this student’s program (has an infinite loop and) will run forever.”Proving that a problem is computable usually, but not always, consists of demonstrating an actual algorithm which will terminate with a correct answer for every input. The amount of resources (time and space) used in the calculation, although finite, is unlimited. Thus, computability gives us an understanding of the capabilities and limitations of the machines that man-kind can build, but without regard to resource restrictions.

In contrast to this, computational complexity deals precisely with the quantitative aspects of problem solving. It addresses the issue of what can be computed within a practical or reasonable amount of time and space by measuring the resource requirements exactly or by obtaining upper and lower bounds. Complexity is actually determined on three levels: the problem, the algorithm, and the implementation. Naturally, we want the best algorithm which solves our problem, and we want to choose the best implementation of that algorithm.

A problem consists of a question to be answered, a requirement to be fulfilled, or a best possible situation or structure to be found, called a solution, usually in response to several input parameters or variables, which are described but whose values are left unspecified. A decision problem is one which requires a simple “yes” or “no” answer. An instance of a problem Π is a specification of particular values for its parameters. An algorithm for Π is a step-by-step procedure which when applied to any instance of Π produces a solution.

Usually we can rewrite an optimization problem as a decision problem which at first seems to be much easier to solve than the original but turns out to be just about as hard. Consider the following two versions of the graph coloring problem.

GRAPH COLORING (optimization version)

Instance: An undirected graph G.

Question: What is the smallest number of colors needed for a proper coloring of G?

GRAPH COLORING (decision version)

Instance: An undirected graph G and an integer k > 0.

Question: Does there exist a proper k coloring of G?

The optimization version can be solved by applying an algorithm for the decision version n times for an n-vertex graph. If the n decision problems are solved sequentially, then the time needed to solve the optimization version is larger than that for the decision version by at most a factor of n. However, if they can be solved simultaneously (in parallel), then the time needed for both versions is essentially the same.

It is customary to express complexity as a function of the size of the input. We say that an algorithm for Π runs in time O(f(m)) if for some constant c > 0 there exists an implementation of which terminates after at most cf (m) (computational) steps for all instances of size m. The complexity of an algorithm is the smallest function f such that runs in O(f(m)). The complexity of a problem Π is the smallest function f for which there exists an O(f(m))-time algorithm for Π, i.e., the minimum complexity over all possible algorithms solving Π. Thus, demonstrating and analyzing the complexity of a particular algorithm for Π provides us with an upper bound on the complexity of Π.*

By presenting faster and more efficient algorithms and implementations of algorithms, successive researchers have improved the complexity upper bounds (i.e., lowered them) for many problems in recent years. Consider the example of testing a graph for planarity. A graph is planar if it can be drawn on the plane (or on the surface of a sphere) such that no two edges cross one another. Kuratowski’ s [1930] characterization of planar graphs in terms of forbidden configurations provides an obvious exponential-time planarity algorithm, namely, verify that no subset of vertices induces a subgraph homeomorphic to K5 or K3¯. Auslander and Parter [1961] gave a planar embedding procedure, which Goldstein [1963] was able to formulate in such a way that halting was guaranteed. Shirey [1969] implemented this algorithm to run in O(n3) time for an n-vertex graph. In the meantime, Lempel, Even, and Cederbaum [1967] gave a different planarity algorithm, and, although they did not specify a time bound, an easy O(n2) implementation exists. Hopcroft and Tarjan [1972, 1974] then improved the Auslnder-Parter method first to O(n log n) and finally to O(n), which is the best possible. Booth and Leuker showed that the Lempel–Even–Cederbaum method could also be implemented to run in O(n) time. Table 2.1 shows the stages of improvement for the planarity problem and for the maximum-network-flow problem. Tarjan [1978] summarizes the progress on a number of other problems.