SIGEST

Probably the most famous concepts in theoretical computer science are the notions of P and NP. A problem is “in P” if it can be solved in polynomial time (as a function of the length of the input) for any problem input, whereas a problem “in NP” can be solved in nondeterministic polynomial time (meaning that for any problem input, it can be determined in polynomial time whether any specific candidate solution is correct or not). Generally, if a problem is in P, this means that there is an efficient algorithm to solve the problem, while if it is in NP, there is an efficient algorithm to check whether a potential solution actually is a solution. An example of a problem in NP (given in www.claymath.org/millennium/P_vs_NP) arises when, for a pool of 400 students, one wishes to assign 100 of them to two-person dormitory rooms while respecting a specified list of pairs of incompatible students. For any list of room assignments for 100 given students, it is not difficult to efficiently check whether the incompatibilities are violated, yet there is no known polynomial time algorithm that is guaranteed to generate an acceptable list of room assignments from scratch. From the P-NP taxonomy has arisen the famous “P = NP?” question, the still unresolved issue of whether these two problem classes are the same; that is, whether all problems that can be solved in nondeterministic polynomial time can be solved in deterministic polynomial time. And stemming from this question are the classes of NP-complete and NP-hard problems. NP-complete problems are problems that are computable in nondeterministic polynomial time (i.e., that are in NP) and for which, if there is a deterministic polynomial algorithm (i.e., the problem is in P), then there is a deterministic polynomial algorithm for all problems in NP. NP-hard problems are problems that satisfy the second portion of the previous statement (existence of a deterministic polynomial time algorithm for that problem implies that P = NP) but not necessarily the first portion (they are not necessarily in NP). That is, NP-hard problems may be even harder than NP-complete problems. One of the reasons that these categorizations are so important is that many problems of great practical interest are NP-complete or NP-hard. One consequence of this fact is that if the “P = NP?” question were solved affirmatively, this might lead to much more efficient worst-case algorithms (i.e., algorithms that are efficient for any problem input) for many important real-world problems. For instance, many cryptographic protocols, like RSA encryption, would be insecure, since adversaries could decrypt messages efficiently without knowing the secret key. A different consequence is that, at present, the known worst-case algorithms for most NP-complete or NP-hard problems are computationally infeasible, so that “approximation algorithms” are sought to use instead. Approximation algorithms typically may not find the best solution to the problem, but they are guaranteed to find a solution that is provably close to the optimum solution, in a reasonable (polynomial) amount of time. This issue's SIGEST paper takes a large step in this arena. It considers the minimum bisection problem, an NP-hard problem that is a building block for many graph algorithms and practical problems in areas ranging from VLSI design to image processing. Minimum bisection is the problem of partitioning the vertices of a graph into two sets with half the vertices each, with the least number of edges connecting nodes in one set to nodes in the other. Needless to say, there is no known polynomial time algorithm for this problem (otherwise P would equal NP) and it is very expensive to solve. In addition, until this paper, no polynomial time algorithm was known that computed a nearly optimal solution to the minimum bisection problem in all cases. Indeed, this question had been unresolved for over twenty years and listed on many open problem lists. Uriel Feige and Robert Krauthgamer, in the paper “A Polylogarithmic Approximation of Minimum Bisection,” initially published in the SIAM Journal on Computing, 31 (2002), pp. 1090–1118, provide a polynomial time algorithm that finds a bisection of any graph whose cost (number of edges connecting the two equal subsets of vertices) is within a factor of O(log$^{\mbox{\scriptsize 1.5}}$n) (that is, a fixed constant times the 1.5 power of the logarithm of the number of vertices) from the minimum cost. (Note that the bound in the 2002 version of the paper is O(log$^{\mbox{\scriptsize 2}}$n); as the authors explain after Theorem 1.1, the power now has been reduced from 2 to 1.5 because the bound is actually log n times the best known approximation ratio for min-ratio cuts, and the latter has been reduced from log n to $\sqrt{\mbox{log \textit{n}}}$ in recent work by Arora, Rao, and Varizani.) They also produce a tighter bound of O(log n) for graphs excluding any fixed graph (e.g., planar graph) as a “subcomponent,” and extend their results to several generalizations of the minimum bisection problem. The importance of this paper already has been recognized by its recent selection for the 2005 SIAM Outstanding Paper Award. As one might expect, it is quite technical, but very nicely organized so that interested readers from a variety of areas can get a sense of the basic concepts and proof techniques. We are delighted to present all SIAM Review readers with this glimpse into the latest results and techniques in the theory of computing.