8.2 TYPICAL NP PROBLEMS 221associating with each node of the graph a different color, usually represented
by some integer. The complexity of the problem comes from the requirement
that for every edge of the graph, the nodes at the two ends must have different
colors. It should be obvious that if there are N nodes in the graph, we can
color the graph with N different colors, but can we do any better? As an opti-
mization problem, we ask what is the smallest number of colors that are
needed to color a given graph. As a decision problem, we ask if a graph can be
colored with C colors or less.
Graph coloring can have practical applications. If we assign every course
offered at a college to a node and add edges between every pair of nodes for
the courses each student is taking, we have a rather complex graph. Given that
most students take 5 courses, there would be 10 edges added for each student.
Let’s say that there are 500 different courses offered and about 3500 students.
That means the final graph would have 500 nodes and 35,000 edges. We can
now associate each exam week slot with a different color. If there are 20 slots,
we try to produce a coloring of the graph with 20 different colors. Assigning
different colors or exam slots to the nodes at the opposite ends of an edge
means that those two courses cannot have exams at the same time, and so the
student cannot have a conflict between these two exams.
Creating an exam schedule with no conflicts is the equivalent of the graph
coloring problem. But because graph coloring is an NP problem, it is not pos-
sible to produce a conflict-free exam schedule in any reasonable amount of
time. Additionally, exam scheduling typically tries to limit students to no more
than two exams in one day and to schedule multiple sections of a course at the
same time. This would place further limits on the color options at each node.
Obviously, because creating the “perfect” exam schedule is impossible, there
must be another technique used to get exam schedules that are as good as they
are. Approximation algorithms will be discussed in Chapter 9.
■ 8.2.2 Bin Packing
We have a number of bins each with a capacity of 1, and we have a set of
objects all with different sizes, s 1 ,s 2 ,... , sN between 0 and 1. The optimization
problem asks what is the fewest number of bins that would be needed to store
all of these objects, and the decision problem would ask if it is possible to store
all of the objects in B bins or less.
This problem can be related to storing information on disks or in frag-
mented computer memory banks, to shipping companies who would like to