# Chapter 11

## Contents

# NP-Completeness

### Transformations and Satisfiability

- 11.1. Give the 3-SAT formula that results from applying the reduction of SAT to 3-SAT for the formula:

- 11.2. Draw the graph that results from the reduction of 3-SAT to vertex cover for the expression

- 11.3. Prove that 4-SAT is NP-hard.

- 11.4.
*Stingy*SAT is the following problem: given a set of clauses (each a disjunction of literals) and an integer , find a satisfying assignment in which at most variables are true, if such an assignment exists. Prove that stingy SAT is NP-hard.

- 11.5. The
*Double SAT*problem asks whether a given satisfiability problem has**at least two different satisfying assignments**. For example, the problem is satisfiable, but has only one solution . In contrast, has exactly two solutions. Show that Double-SAT is NP-hard.

- 11.6. Suppose we are given a subroutine that can solve the traveling salesman decision problem on page 357 in (say) linear time. Give an efficient algorithm to find the actual TSP tour by making a polynomial number of calls to this subroutine.

- 11.7. Implement a SAT to 3-SAT reduction that translates satisfiability instances into equivalent 3-SAT instances.

- 11.8. Design and implement a backtracking algorithm to test whether a set of clause sets is satisfiable. What criteria can you use to prune this search?

- 11.9. Implement the vertex cover to satisfiability reduction, and run the resulting clauses through a satisfiability solver code. Does this seem like a practical way to compute things?

### Basic Reductions

- 11.10. An instance of the
*set cover*problem consists of a set of elements, a family of subsets of , and an integer . The question is, does there exist subsets from whose union is ? For example, if and , there does not exist a solution for , but there does for (for example, ). Prove that set cover is NP-complete with a reduction from vertex cover.

- 11.11. The
*baseball card collector problem*is as follows. Given packets , each of which contains a subset of this year's baseball cards, is it possible to collect all the year's cards by buying packets? For example, if the players are and the packets are - there does not exist a solution for , but there does for , such as
- Prove that the baseball card collector problem is NP hard using a reduction from vertex cover.

- 11.12. The
*low-degree spanning tree problem*is as follows. Given a graph and an integer , does contain a spanning tree such that all vertices in the tree have degree*at most*(obviously, only tree edges count towards the degree)? For example, in the following graph, there is no spanning tree such that all vertices have a degree less than three.

\fixedfigsize{pictures/lowdegree.png}{1.0in}

- Prove that the low-degree spanning tree problem is NP-hard with a reduction from Hamiltonian
*path*. - Now consider the
*high-degree spanning tree problem*, which is as follows. Given a graph and an integer , does contain a spanning tree whose highest degree vertex is*at least*? In the previous example, there exists a spanning tree with a highest degree of 8. Give an efficient algorithm to solve the high-degree spanning tree problem, and an analysis of its time complexity.

- 11.14

- 11.16

- 11.18

- 11.20

### Creatvie Reductions

- 11.22

- 11.24

- 11.26

- 11.28

- 11.30

### Algorithms for Special Cases

- 11.32

- 11.34

Back to Chapter List