Complexity Classes - Models of Computation: Exploring the Power of Computing - page 386

instance of SATISFIABILITY in which each clause is a Horn clause. Show that HORN
SATISFIABILITY is in P .
Hint: If all literals in a clause are negative, the clause is satisfied only if some associated
va ri a bles ha ve value 0. If a clause has one positive literal, say y , and negative literals, say
x 1 , x 2 , ... , x k , then the clause is satisfied if and only if the implication x 1 ∧ x 2 ∧···∧

x k ⇒ y is true. Thus, y has value 1 when each of these variables has value 1. Let T

be a set variables that must have value 1. Let contain initially all positive literals that

appear alone in a clause. Cycle through all implications and for each implication all
of whose left-hand side variables appear in

T

T

but whose right-hand side variable does

T T

not, add this variable to grows until all left-hand sides are satisfied, this

procedure terminates. Show that all satisfying assignments contain

.Since

T

.
8.23 Describe a polynomial-time algorithm to determine whether an instance of CIRCUIT
SAT is a “yes” instance when the circuit in question consists of a layer of AND gates
followed by a layer of OR gates. Inputs are connected to AND gates and the output gate
is an OR gate.
8.24 Prove that the CLIQUE problem defined below is NP -complete.

CLIQUE
Instance: The description of an undirected graph G =( V , E ) and an integer k .
Answer: “Yes” if there is a set of k vertices of G such that all vertices are adjacent.

8.25 Prove that the HALF CLIQUE problem defined below is NP -complete.

HALF CLIQUE
Instance: The description of an undirected graph G =( V , E ) in which | V | is even and

an integer k .
Answer: “Yes” if G contains a clique on

| V | / 2 vertices or has more than k edges.

Hint: Try reducing an instance of CLIQUE on a graph with m vertices and a clique of
size k to this problem by expanding the number of vertices and edges to create a graph
that has / 2. Show that a test for the condition

that G contains more than k edges can be done very efficiently by counting the number
of bits among the variables describing edges.
8.26 Show that the NODE COVER problem defined below is NP -complete.

| V |≥ m vertices and a clique of size | V |

NODE COVER
Instance: The description of an indirected graph G =( V , E ) and an integer k .
Answer: “Yes”ifthereisasetof k vertices such that every edge contains at least one of
these vertices.

8.27 Prove that the HAMILTONIAN PATH decision problem defined below is NP -complete.

HAMILTONIAN PATH
Instance: The description of an undirected graph G .
Answer: “Yes” if there is a path visiting each node once.

Hint: 3- SAT can be reduced to HAMILTONIAN PATH , but the construction is chal-
lenging. First, add literals to clauses in an instance of 3- SAT so that each clause has