Source code online books for professionals by professionals

partitioning into cliques).  
A clique is, as you may recall, simply a complete graph, although the term is normally used when referring to a 
complete subgraph. In this case, we want to split a graph into cliques. In other words, we want to divide the nodes into 
several (nonoverlapping) sets so that within each set, every node is connected to every other. I’ll show you why this is  
NP-hard in a minute, but first, let’s have a closer look at cliques.
Simply determining whether a graph has a clique of a given size is NP-complete. Let’s say you’re analyzing a 
social network and you want to see whether there’s a group of k people, where every person is friends with every other. 
Not so easy … The optimization version, max-clique, is at least as hard, of course. The reduction from 3-SAT to the 
clique problem once again involves creating a simulation of logical variables and clauses. The idea here is to use three 
nodes for each clause (one for each literal, whether it be a variable or its negation) and then add edges between all 
nodes representing compatible literals, that is, those that can be true at the same time. (In other words, you add edges 
between all nodes except between a variable and its negation, such as A and not A.)
You do not, however, add edges inside a clause. That way, if you have k clauses and you’re looking for a clique 
of size k, you’re forcing at least one node from each clause to be in the clique. Such a clique would then represent a 
valid assignment of truth values to the variables, and you’d have solved 3-SAT by finding a clique. (Cormen et al. give a 
detailed proof; see “References” in Chapter 1.)
The clique problem has a very close relative—a yin to its yang, if you will—called the independent set problem. 
Here, the challenge is to find a set of k independent nodes (that is, nodes that don’t have any edges to each other). The 
optimization version is to find the largest independent set in the graph. This problem has applications to scheduling 
resources, just like graph coloring. For example, you might have some form of traffic system where various lanes in 
an intersection are said to be in conflict if they can’t be in use at the same time. You slap together a graph with edges 
representing conflicts, and the largest independent set will give you the largest number of lanes that can be in use at any 
one time. (More useful in this case, of course, would be to find a partition into independent sets; I’ll get back to that.)
Do you see the family resemblance to clique? Right. It’s exactly the same, except that instead of edges, we now 
want the absence of edges. To solve the independent set problem, we can simply solve the clique problem on the 
complement of the graph—where every edge has been removed and every missing edge has been added. (In other 
words, every truth value in the adjacency matrix has been inverted.) Similarly, we can solve the clique problem using 
the independent set problem—so we’ve reduced both ways.
Now let’s return to the idea of a clique cover. As I’m sure you can see, we might just as well look for an 
independent set cover in the complement graph (that is, a partitioning of the nodes into independent sets). The point 
of the problem is to find a cover consisting of k cliques (or independent sets), with the optimization version trying 
to minimize k. Notice that there are no conflicts (edges) inside an independent set, so all nodes in the same set can 
receive the same color. In other words, finding a k-clique-partition is essentially equivalent to finding a k-coloring, 
which we know is NP-complete. Equivalently, both optimization versions are NP-hard.
Another kind of cover is a vertex (or node) cover, which consists of a subset of the nodes in the graph and covers 
the edges. That is, each edge in the graph is incident to at least one node in the cover. The decision problem asks you 
to find a vertex cover consisting of at most k nodes. What we’ll see in a minute is that this happens exactly when the 
graph has an independent set consisting of at least n-k nodes, where n is the total number of nodes in the graph.  
This gives us a reduction that goes both ways, just like the one between cliques and independent sets.

---

Chapter 11 
■
 hard problems and (lImIted) sloppIness
242
The reduction is straightforward enough. Basically, a set of nodes is a vertex cover if and only if the remaining 
nodes form an independent set. Consider any pair of nodes that are not in the vertex cover. If there were an edge 
between them, it would not have been covered (a contradiction), so there cannot be an edge between them. Because 
this holds for any pair of nodes outside the cover, these nodes form an independent set. (A single node would work on 
its own, of course.)
The implication goes the other way as well. Let’s say you have an independent set—do you see why the remaining 
nodes must form a vertex cover? Of course, any edge not connected to the independent set will be covered by the 
remaining nodes. But what if an edge is connected to one of your independent nodes? Well, its other end can’t be in 
the independent set (those nodes aren’t connected), and that means that the edge is covered by an outside node.  
In other words, the vertex cover problem is NP-complete (or NP-hard, in its optimization version).
Finally, we have the set covering problem, which asks you to find a so-called set cover of size at most k (or, in the 
optimization version, to find the smallest one). Basically, you have a set S and another set F, consisting of subsets of S. 
The union of all the sets in F is equal to S. You’re trying to find a small subset of F that covers all the elements of S.  
To get an intuitive understanding of this, you can think of it in terms of nodes and edges. If S were the nodes of a 
graph, and F, the edges (that is, pairs of nodes), you’d be trying to find the smallest number of edges that would cover 
(be incident to) all the nodes.
Caution
 
■
   the example used here is the so-called edge cover problem. although it’s a useful illustration of the set 
covering problem, you should not conclude that the edge cover problem is np-complete. It can, in fact, be solved in 
polynomial time.
It should be easy enough to see that the set covering problem is NP-hard, because the vertex cover problem 
is basically a special case. Just let S be the edges of a graph and F consist of the neighbor sets for every node, and 
you’re done.
Paths and Circuits
This is our final group of beasties—and we’re drawing near to the problem that started the book. This material mainly 
has to do with navigating efficiently, when there are requirements on locations (or states) you have to pass through. 
For example, you might try to work out movement patterns for an industrial robot, or the layout of some kinds of 
electronic circuits. Once more you may have to settle for approximations or special cases. I’ve already shown how 
finding a Hamilton cycle in general is a daunting prospect. Now let’s see if we can shake out some other hard path and 
circuit-related problems from this knowledge.
First, let’s consider the issue of direction. The proof I gave that checking for Hamilton cycles was NP-complete 
was based on using a directed graph (and, thus, finding a directed cycle). What about the undirected case? It might 
seem we lose some information, and the earlier proof doesn’t hold here. However, with some widgetry, we can 
simulate direction with an undirected graph!
The idea is to split every node in the directed graph into three, basically replacing it by a length-two path. 
Imagine coloring the nodes: You color the original node blue, but you add a red in-node and a green out-node.  
All directed in-edges now become undirected edges linked to the red in-node, and the out-edges are linked to the 
green out-node. Clearly, if the original graph had a Hamilton cycle, the new one will as well. The challenge is getting 
the implication the other way—we need “if and only if” for the reduction to be valid.
Imagine that our new graph does have a Hamilton cycle. The node colors of this cycle would be either  
“… red, blue, green, red, blue, green …” or “… green, blue, red, green, blue, red …” In the first case, the blue nodes 
will represent a directed Hamilton cycle in the original graph, as they are entered only through their in-nodes 
(representing the original in-edges) and left through out-nodes. In the second case, the blue nodes will represent a 
reverse directed Hamilton cycle—which also tells us what we need to know (that is, that we have a usable directed 
Hamilton cycle in the other direction).

---

Chapter 11 
■
 hard problems and (lImIted) sloppIness
243
So, now we know that directed and undirected Hamilton cycles are basically equivalent (see Exercise 11-8).  
What about the so-called Hamilton path problem? This is similar to the cycle problem, except you’re no longer required 
to end up where you started. Seems like it might be a bit easier? Sorry. No dice. If you can find a Hamilton path, you can 
use that to find a Hamilton cycle. Let’s consider the directed case (see Exercise 11-9 for the undirected case). Take any 
node v with both in- and out-edges. (If there is no such node, there can be no Hamilton cycle.) Split it into two nodes,