next up previous
Next: How is the compendium Up: How to find the Previous: A compendium of NP

How is the compendium structured?

We have chosen to structure the problems in the same way as Garey and Johnson did [6], that is systematically in twelve categories according to subject matter. The first five categories are divided into subcategories. The following table shows how many problems there are in each category in the August 1998 version of the compendium, compared to how many there are in [6].

Code Name of category Number of problems in
    G&J [6] compendium
GT Graph theory 65 55
ND Network design 51 65
SP Sets and partitions 21 14
SR Storage and retrieval 36 10
SS Sequencing and scheduling 22 20
MP Mathematical programming 13 17
AN Algebra and number theory 18 1
GP Games and puzzles 15 2
LO Logic 19 13
AL Automata and language theory 21 5
PO Program optimization 10 2
MS Miscellaneous 19 17

For many categories the numbers are about the same. This might be surprising considering that only some of the NP-complete problems in [6] have corresponding optimization problems. The explanation is of course that several new NP-complete problems have been studied since 1979: an updated list of NP-complete problems would be much larger than the original one.

It is interesting that, in some categories, there are much fewer problems in the compendium than in [6]. The reason could either be that there are only a few optimization problems in these categories or that no approximability results have been shown for the optimization problems in these classes. The latter case suggests that more research is needed for these categories.

The current version of the compendium thus contains more than 200 problems. However, under the same basic problem, several variations are also included. A typical entry consists of eight parts: the first four parts are mandatory while the rest are optional.

The problem name that also specifies the goal of the problem.

The definition of the instances of the problem.

The definition of the feasible solutions of the problem.

The definition of the measure of a feasible solution.

A `good news' part that contains the best approximation positive result (upper bound) for the problem.

A `bad news' part that contains the worst approximation negative result (lower bound) for the problem.

A section of additional comments. In this section approximability results for variations of the problem are mentioned.

A reference to the `closest' problem appearing in the list published in [6].

The following is an example of what an entry looks like.

Graph $G=\left<V,E\right>$.

A coloring of E, that is, a partition of E into disjoint sets $E_1,E_2,\ldots,E_k$ such that, for $1\le i\le k$, no two edges in Ei share a common endpoint in G.

Cardinality of the coloring, i.e., the number of disjoint sets Ei.

Good News:
Approximable within 4/3, and even approximable with an absolute error guarantee of 1 [14].

Bad News:
Not approximable within 4/3$-\varepsilon $ for any $\varepsilon >0$ [8].

Also called Minimum Chromatic Index. APX-intermediate unless the polynomial-hierarchy collapses [4]. On multigraphs the problem is approximable within 1.1 $+(0.8/\mbox{\sl opt})$ [11]. The maximization variation in which the input is extended with a positive integer k, and the problem is to find the maximum number of consistent vertices over all edge-colorings with k colors, is approximable within e/(e-1) [3], but does not admit a PTAS [12].

Garey and Johnson:

next up previous
Next: How is the compendium Up: How to find the Previous: A compendium of NP
Viggo Kann