228 NONDETERMINISTIC ALGORITHMS
return yes
else
return no
end if
The requirement of the class NP is that we are able to check the proposed
solution in polynomial time. You should see that this algorithm properly checks
the penalties for the list of jobs provided. If we analyze the time complexity of
this algorithm, we see that the while loop will do at most N passes if the
currentPenalty is never increased. If we count all of the work, there will
be 3N + 1 comparisons and at most 3N additions. This means that this algo-
rithm is in O(N), which is clearly polynomial and meets our requirements.■ 8.4.2 Graph Coloring
The graph coloring problem attempts to determine how to assign colors (rep-
resented as integers) to the nodes of the graph so that no two nodes that are
connected by a single edge have the same color. You will recall that the deci-
sion version of this problem tries to determine if the graph can be colored in C
colors or less, whereas the optimization version tries to determine the smallest
number of colors needed.
Our nondeterministic step will produce a proposed solution that will be a
list of the nodes and the colors assigned to them. The nondeterministic step
will be responsible for deciding how many colors to use, so that’s not some-
thing we need to check. For the decision problem, the nondeterministic step
will try to assign at most C colors. For the optimization problem, it might start
with a large number of colors and keep decreasing it as long as a valid coloring
is still possible. Then when it determines that the graph can’t be colored with
X colors, it knows that X + 1 is the minimal number of colors required.
The following algorithm will check to see if the colors proposed are a valid
way to color the graph. This algorithm uses an adjacency list to hold the graph,
so that graph[j] represents the jth node of the graph, graph[j].edge-
Count represents the number of edges leaving node j, and graph[j].edge is
an array with the nodes that are adjacent to node j.
boolean
ValidColoring( graph, N, colors )
graph the adjacency list
N the number of nodes in the graph
colors the array of colors assigned to each node