The NP-completeness column: An ongoing guide

This is the fifteenth edition of a quarterly column that covers new developments in the theory of NP-completeness. The presentation is modeled on that used by M. R. Garey and myself 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 will be referred to by their dates). A background equivalent to that provided by [G & J] is assumed, and, when appropriate, cross-references will be given to that book and the list of problems (NP-complete and harder) presented there. Readers who have results they would like mentioned (NP-hardness, PSPACE-hardness, polynomial-time-solvability, etc.) or open problems they would like publicized, should send them to David S. Johnson, Room 2C-355, AT & T Bell Laboratories, Murray Hill, NJ 07974 (CSNET address: dsj.btl@csnet-relay). Please include details, or at least sketches, of any new proofs; full papers are preferred. If the results are unpublished, please state explicitly that you would like them to be mentioned in the column. Comments and corrections are also welcome. For more details on the nature of the column and the form of desired submissions, see the December 1981 issue of this Journal.