The NP-completeness column

Published in ACM TRANSACTIONS ON ALGORITHMS 1:1, 160-176 (2005)

The NP-Completeness Column

DAVID S. JOHNSON

AT&T Labs – Research, Florham Park, New Jersey

Abstract. This is the 24th edition of a column that covers new developments in the theory of

NP-completeness. The presentation is modeled on that which M. R. Garey and I used in our book

“Computers and Intractability: A Guide to the Theory of NP-Completeness,” W. H. Freeman &

Co., New York, 1979, hereinafter referred to as “[G&J].” Previous columns, the first 23 of which

appeared in J. Algorithms, will be referred to by a combination of their sequence number and year

Additional Key Words and Phrases: NP-completeness, open problems, primality testing, perfect

graphs, coding theory, lattice bases

1. A BELATED REVIVAL

With this article, I resume a long-dormant column on NP-completeness whose first

23 editions appeared in J. Algorithms from 1981 through 1992. When the column

first appeared, just two and a half years after the publication of [G&J], its main

purpose was to provide timely additions and updates to the list of NP-complete

and open problems at the end of that book. As the column evolved, however,

it tended to devote more of its effort to providing brief reports and tutorials on

new theoretical developments related to NP-completeness, covering such topics as

Transactions on Algorithms as a successor to J. Algorithms. In addition, I hope

that the research I do in preparing the column will help me make progress on a

planned 2nd edition of [G&J]. Much has happened in the 13 years since the last

Author’s address: Room C239, AT&T Labs - Research, 180 Park Avenue, Florham Park, NJ

07932, e-mail: dsj@research.att.com.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is

granted without fee provided that copies are not made or distributed for profit or direct commercial

advantage and that copies show this notice on the first page or initial screen of a display along

with the full citation. Copyrights for components of this work owned by others than ACM must

be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on

Table I. The current status of the open problems from [G&J] and previous columns.

Problem Name Source Status Covered in

GRAPH ISOMORPHISM [G&J] Open –

SUBGRAPH HOMEOMORPHISM [G&J] P [Col 19, 1987]

(FOR A FIXED GRAPH H)

GRAPH GENUS [G&J] NPC [Col 21, 1988]

CHORDAL GRAPH COMPLETION [G&J] NPC [Col 1, 1981]

CHROMATIC INDEX [G&J] NPC [Col 1, 1981]

PARTIAL ORDER DIMENSION [G&J] NPC [Col 1, 1981]

MINIMUM LENGTH TRIANGULATION [G&J] Open –

IMPERFECT GRAPH [Col 1, 1981] P This Column

GRAPH THICKNESS [Col 2, 1982] NPC [Col 5, 1982]

EVEN COVER [Col 3, 1982] NPC This Column

(MINIMUM WEIGHT CODEWORD)

“UNRESTRICTED” TWO-LAYER [Col 5, 1982] Open –

CHANNEL ROUTING

GRACEFUL GRAPH [Col 6, 1983] Open –

ANDREEV’S PROBLEM [Col 17, 1986] Open –

SHORTEST VECTOR IN A LATTICE [Col 18, 1986] “NPC” This Column

1992, and their resolutions were covered in previous columns. Since then one of the

four open problems from [G&J] and two of the open problems from the columns

have been resolved, and one of the column problems has been partially resolved

(in a sense to be explained later). Section 2 will cover the resolved and partially

resolved problems, while Section 3 will discuss the problems that remain open. The

next column will likely cover hardness-of-approximation results and the complexity

conjectures on which they rely. Suggestions of topics and results to be covered by

future columns are welcome.

While readers await the next column, they might wish to investigate some of the

many other sources that now provide information about developments in the field.

Scott Aaronson, is a delightful survey of the wide variety of proposals for using

physical processes to obtain exponential speedups over classical Turing machines

and thus solve NP-complete problems efficiently. It covers a wide variety of sug-

gestions, from soap bubbles to various exploitations of quantum mechanics, and

explains why each is unlikely to work.

A second relevant column has been appearing regularly in the Bulletin of the

EATCS since 1987. Originally entitled “The Structural Complexity Column” and

moderated by Juris Hartmanis, it morphed in 1997 into “The Complexity Column,”

moderated first by Eric Allender, then by Lance Fortnow, and currently by Jacobo

Tor´an. An index and downloadable .pdf versions of recent editions are available

gust 2002, with daily updates. This is where many of us first hear about major

results, and where we could even find technical reviews of the early episodes of the

CBS television series Numb3rs, in the second episode of which the question of P ver-

sus NP played a central role. A webpage maintained by Scott Aaronson, “The Com-

plexity Zoo” (http://www.complexityzoo.com) provides notation and definitions

for hundreds of complexity classes, both common and obscure, along with some of

the facts known about them. Pierluigi Crescenzi and Viggo Kann maintain an “NP

Optimization Problem” website (http://ww.nada.kth.se/∼viggo/problemlist

least through March 2000. Gerhard Woeginger maintains “The P-versus-NP”

Finally, readers who have not seen the earlier editions of this column (or have

forgotten them) can now obtain them online. I recently compiled .pdf versions

of all 23 columns from the original troff source files, and have posted them at

slightly different pagination and some subpar equation formatting due to changes

in the underlying typesetting software. In addition, the figures in Columns 5 and

16 had to be recreated because the software that originally generated them was no

longer functional. (Oh, the joys of software evolution!) Definitive electronic versions

of the columns can be found at Science Direct (http://www.sciencedirect.com),