Reduction of Boolean 3-Sat to Vertex Cover.


Suppose that E is a boolean expression in conjunction normal form, where
there are n clauses.  Each clause consists of three terms, and each term
is either a variable or the negation of a variable.  Let m be the number
of distinct variables.  Note that m = O(n).  Let x_1 , .... x_m be
those variables.  Thus each term is the form x_i or ~x_i for some i.
Without loss of generality, the three variables of each clause are
distinct.

We now design a graph G with 4m(m+1) vertices and 5m^2 + 6m + n edges,
such that G has a (3m^2/2 + 5m/2)-vertex covering if and only if E is
satisfiable.

There are two classes of vertex, which we "singletons" and "doubletons."
Each vertex is labeled by a boolean expression.  A singleton is
labeled either x_i or ~x_i for some i.  Thus, there are 2m singleton
vertices.  A doubleton is labeled either x_i + x_j, x_i + ~x_j,
~x_i + x_j, or ~x_i + ~x_j, for some i < j.

We then create edges between pairs of vertices, labeling each vertex with
a boolean expression which is the disjunction of the boolean expressions
of its end vertices.

There are four classes of edges, as follows:

	Class I.  For each i, an edge between x_i and ~x_i.  This edge is
labeled with the boolean expression x_i + ~x_i.  There are m edges in
this class.

	Class II.  For each i < j, we create 8 edges as follows:
		a) An edge between x_i and ~x_i + x_j, labeled x_i + x_i + x_j.
		b) An edge between x_i and ~x_i + ~x_j.
		c) An edge between ~x_i and x_i + x_j.
		d) An edge between ~x_i and x_i + ~x_j.
		e) An edge between x_j and x_i + ~x_j.
		f) An edge between x_j and ~x_i + ~x_j.
		g) An edge between ~x_j and x_i + x_j.
		h) An edge between ~x_j and ~x_i + x_j.
There are 4m(m+1) edges in this class.

	Class III.  For each i < j, we create 6 edges as follows:
		a) An edge between x_i + x_j and x_i + ~x_j.
		b) An edge between x_i + x_j and ~x_i + x_j.
		c) An edge between x_i + x_j and ~x_i + ~x_j.
		d) An edge between x_i + ~x_j and ~x_i + x_j.
		e) An edge between x_i + ~x_j and ~x_i + ~x_j.
		f) An edge between ~x_i + x_j and ~x_i + ~x_j.
There are 3m(m+1) edges in this class.

	Class IV.  For any clause of the form t_1+t_2+t_3, we create
one edge between t_1+t_2 and t_3.  There are n edges in this class.

Given any assignment of values to the variables, exactly half, i.e., m,
of the boolean expressions labeling the singleton vertices will be true,
and exactly three fourths, i.e., 3m(m+1)/2, of the boolean expressions
labeling the doubleton vertices will be true.

The boolean expressions that label the edges of Classes I, II, and III
are tautologies.  Given a satisfying assignment, then the boolean expression
labeling each edge of class IV will be true.

Thus, if there is a satisfying assignment, there is a vertex cover
of cardinality k =