# 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:
${\displaystyle (x\lor y\lor {\overline {z}}\lor w\lor u\lor {\overline {v}})\land ({\overline {x}}\lor {\overline {y}}\lor z\lor {\overline {w}}\lor u\lor v)\land (x\lor {\overline {y}}\lor {\overline {z}}\lor w\lor u\lor {\overline {v}})\land (x\lor {\overline {y}})}$

11.2. Draw the graph that results from the reduction of 3-SAT to vertex cover for the expression
${\displaystyle (x\lor {\overline {y}}\lor z)\land ({\overline {x}}\lor y\lor {\overline {z}})\land ({\overline {x}}\lor y\lor z)\land (x\lor {\overline {y}}\lor {\overline {x}})}$

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 ${\displaystyle k}$, find a satisfying assignment in which at most ${\displaystyle k}$ 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 ${\displaystyle {{v1,v2},{v_{1},v_{2}},{v_{1},v_{2}}}}$ is satisfiable, but has only one solution ${\displaystyle (v_{1}=F,v_{2}=T)}$. In contrast, ${\displaystyle {{v_{1},v_{2}},{v_{1},v_{2}}}}$ 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 ${\displaystyle X}$ of ${\displaystyle n}$ elements, a family ${\displaystyle F}$ of subsets of ${\displaystyle X}$, and an integer ${\displaystyle k}$. The question is, does there exist ${\displaystyle k}$ subsets from ${\displaystyle F}$ whose union is ${\displaystyle X}$? For example, if ${\displaystyle X=\{1,2,3,4\}}$ and ${\displaystyle F=\{\{1,2\},\{2,3\},\{4\},\{2,4\}\}}$, there does not exist a solution for ${\displaystyle k=2}$, but there does for ${\displaystyle k=3}$ (for example, ${\displaystyle \{1,2\},\{2,3\},\{4\}}$). 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 ${\displaystyle P_{1},\ldots ,P_{m}}$, each of which contains a subset of this year's baseball cards, is it possible to collect all the year's cards by buying ${\displaystyle \leq k}$ packets? For example, if the players are ${\displaystyle \{Aaron,Mays,Ruth,Steven\}}$ and the packets are
${\displaystyle \{\{Aaron,Mays\},\{Mays,Ruth\},\{Steven\},\{Mays,Steven\}\},}$
there does not exist a solution for ${\displaystyle k=2}$, but there does for ${\displaystyle k=3}$, such as
${\displaystyle \{Aaron,Mays\},\{Mays,Ruth\},\{Steven\}}$
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 ${\displaystyle G}$ and an integer ${\displaystyle k}$, does ${\displaystyle G}$ contain a spanning tree such that all vertices in the tree have degree at most ${\displaystyle k}$ (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}

1. Prove that the low-degree spanning tree problem is NP-hard with a reduction from Hamiltonian path.
2. Now consider the high-degree spanning tree problem, which is as follows. Given a graph ${\displaystyle G}$ and an integer ${\displaystyle k}$, does ${\displaystyle G}$ contain a spanning tree whose highest degree vertex is at least ${\displaystyle k}$? 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.13

11.14

11.15

11.16

11.17

11.18

11.19

11.20

11.21

11.22

11.23

11.24

11.25

11.26

11.27

11.28

11.29

11.30

### Algorithms for Special Cases

11.31

11.32

11.33

11.34

11.35

Back to Chapter List