 Introduction to Automata
Theory, Languages, and Computation

Solutions for Chapter 10
Revised 6/30/01.
Solutions for Section 10.1
Solutions for Section 10.2
Solutions for Section 10.3
Solutions for Section 10.4
Solutions for Section 10.1
Exercise 10.1.1(a)
The MWST would then be the line from 1 to 2 to 3 to 4.
Exercise 10.1.3
For every problem P
in NP there would be some polynomial p
that bounded the running time (and therefore the output length) of the
reduction from P to the NPcomplete problem in question.
That would imply an algorithm for P that ran in time
O(p(n) + [p(n)]^{log_2(p(n))}).
The first term, p(n), can be neglected.
The exponent is k log n for some constant k.
Moreover, p(n)^k is at most n^k' for some other constant
k'.
Thus, we can say that there would be some constant c such
that problem P could be solved in time O(n^{c log_2 n}).
Exercise 10.1.5(a)
Given (G,A,B), construct G1 and G2 to be G,
with start symbols A and B, respectively.
Since this transformation is essentially copying, it can be performed in
linear time, and is therefore surely a polynomialtime reduction.
Exercise 10.1.5(c)
Absolutely nothing!
Part of any NPcompleteness proof is a part that shows the problem to be
in NP.
These problems are, in fact, undecidable, and therefore surely not in
NP.
Exercise 10.1.6(b)
Test for membership in one language and then, if the input is not in the
first, test for membership in the second.
The time taken is no more than the sum of the times taken to recognize
each language.
Since both ar in P, then can each be recognized in polynomial
time, and the sum of polynomials is a polynomial.
Thus, their union is in P.
Exercise 10.1.6(c)
Let L1 and L2 be languages in P, and suppose we
want to recognize their concatenation.
Suppose we are given an input of length n.
For each i between 1 and n1, test whether positions 1
through i holds a string in L1
and positions i+1n hold a
string in L2.
If so, accept; the input is in L1L2.
If the test fails for all i, reject the input.
The running time of this test is at most
n times the sum of the running
times of the recognizers for L1 and L2.
Since the latter are both polynomials, so is the running time for the
TM just described.
Exercise 10.1.6(f)
Given a polynomialtime TM M for L, we can modify M
to accept the complement of L as follows:

Make each accepting state of M a nonaccepting state from which
there are no moves.
Thus, if M accepts, the new TM will halt without accepting.

Create a new state q, which is the only accepting state in the
new TM.
For each statesymbol combination that has no move, hte new TM enters
state q, whereupon it accepts and halts.
Return to Top
Solutions for Section 10.2
Exercise 10.2.1(a)
Choosing x = y = z = 1 makes the expression satisfiable.
Thus, the expression is in SAT.
Exercise 10.2.2(a)
There are actually only three distinct Hamilton circuits, once we account
for the differences in direction and differences in starting point.
These three circuits are (1,2,3,4), (1,3,2,4), and (1,3,4,2).
We can express the existence of one of these three circuits (using the
simplified notation of Section 10.3) by:
x12x23x34x14 + x13x23x24x14 + x13x34x24x12.
Return to Top
Solutions for Section 10.3
Exercise 10.3.1(a)
In what follows, [x] stands for xbar, the complement of
x.
We'll begin by using the construction to put it into CNF.
xy is already the product of clauses (x)(y), and
[x]z is the product of clauses ([x])(z).
When we use the OR construction to combine these, we get
(x+u)(y+u)([x]+[u])(z+[u]).
Now, to put this expression into 3CNF, we have only to expand the four
clauses, each of which has only two literals, by introducing four new
variables and doubling the number of clauses.
The result:
(x+u+v1)(x+u+[v1])(y+u+v2)(y+u+[v2])([x]+[u]+v3)([x]+[u]+[v3])(z+[u]+v4)(z+[u]+[v4]).
Exercise 10.3.3(a)
It is satisfiable.
Let any two variables be assigned TRUE, say x1 and x2, and
let the other two variables be assigned FALSE.
Then in any set of three variables, there must be at least one true and
at least one false.
Thus, none of the clauses can be false.
Return to Top
Solutions for Section 10.4
Exercise 10.4.1
For part (a): There are triangles (3cliques), such as {1,2,3}.
However, there is no 4clique, since there are only 4 nodes, and one
edge is missing.
Thus k = 3 is the answer.
For part (b): All pairs of nodes must have an edge between them, and the
number of pairs of k nodes is k choose 2, or
k(k1)/2.
For part (c): We reduce NC to CLIQUE as follows.
Suppose we are given an instance (G,k) of NC.
Construct the instance (G',nk) of CLIQUE, where n is the
total number of nodes of G, and G' is G with the
set of edges complemented; that is, G' has edge (u,v) if
and only if G does not have that edge.
We must show that G has a node cover of size k if and
only if G' has a clique of size nk.
First, let C be a node cover of G of size k.
We claim that C', the complement of the nodes in C, is a
clique in G' of size nk.
Surely C' is of size nk.
Suppose it is not a clique.
Then there is a pair of nodes (u,v) that do not have an edge in
G'.
Thus this edge is in G.
But neither u nor v is in C, contradicting the
assumption that is is a node cover.
Conversely, if C' is a clique of size nk in G',
then we claim that C the complement of C', is a node cover
of size k in G.
The argument is similar:
if (u,v) is an edge of G not covered by C, then
both u and v are in C', but the edge (u,v)
is not in G', contradicting the assumption that C' is a
clique.
Exercise 10.4.2
For each clause, we add one node, and connect it so that it can only be
colored in one of the n+1 available colors if the clause is made
true.
Suppose the clause consists of literals with variables xi, xj,
and xk, possibly negated.
The node for the clause is connected to:

xm for all m = 0, 1,..., n, except for i, j,
and k.
Thus, the only possible colors for the nodes are the ones used for its
literals.

If the literal with xi is positive (not negated), connect the
node for the clause to the node for xI.
If the literal is negated, connect the node for the clause to the node
for xibar.

Connect to nodes for xj and xk, analogously.
Now, if at least one of the literals of the clause is made true by the
assignment where the color c0 corresponds to truth, then that
literal will not be colored with the color for its variable, and we can
use that color for the clause's node.
However, if the truth assignment makes all three literals false, then
the clause's node is connected to nodes of all n+1 colors, and we
cannot complete the coloring.
Thus, coloring the complete graph with n+1 colors is possible if
and only if there is a satisfying truth assignment for the 3CNF
expression.
Exercise 10.4.3(a)
Yes; a Hamilton circuit can be found by going around the inner circle,
say from 11 to 20, clockwise, then to 10, around the outer circle
counterclockwise, to 1, and then back to 11.
Exercise 10.4.4(f)
Let (G,k) be an instance of the clique problem, and suppose
G has n nodes.
We produce an instance of the halfclique problem, as follows:

If k = n/2, just produce G.
Note that G has a halfclique if and only if it has a clique of
size k. in this case.

If k > n/2, add 2k  n isolated nodes (nodes with no
incident edges).
The resulting graph has a halfclique (whose size must be
(n + (2kn))/2
= 2k, if and only if G has a clique of size k.

If k < n/2, add n  2k nodes, and connect them in all
possible ways to each other and to the original nodes of G.
The new graph thus has 2(nk) nodes.
The new nodes, plus a clique of size k in G form a clique
of size (n2k) + k = nk, which is half the number of nodes in
the new graph.
Conversely, if the new graph has a halfclique, then it must include at
least (nk)  (n2k) = k nodes of the graph G, implying
that G has a clique of size k.
These steps complete a reduction of CLIQUE to HALFCLIQUE.
It is evidently performable in polynomial time, since the number of new
nodes and edges is at most the square of the original number of nodes,
and the rules for adding nodes and edges are simple to carry out.
Exercise 10.4.5(a)
Following the hint, pick any node x in graph G.
Add a duplicate node y that is adjacent to exactly those nodes
to which x is adjacent.
Then, add new nodes u and v that are adjacent to x
and y, respectively, and no other nodes.
Call the resulting graph G'.
We claim G' has a Hamilton path if and only if G has a
Hamilton circuit.
If G has a Hamilton circuit, the following is a Hamilton path in
G':
start at u, go to x, follow the Hamilton circuit, but end
at y instead of x, and then go to v.
If G' has a Hamilton path, it must start at u and end at
v, or viceversa (which is really the same path.
Moreover, the path must go from xy, visiting all the
nodes of G as it does.
Thus, if we replace y by x along this path, we get a
Hamilton circuit in G.
Exercise 10.4.5(c)
A spanning tree with two leaf nodes is a Hamilton path.
Thus, the Hamilton path problem reduces to the question of whether a
graph has a spanning tree with only 2 leaf nodes.
Surely, then, Hamilton path reduces to the more general problem stated
in the question, where the number of leaf nodes is a parameter of the
problem.
Return to Top