# 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\or y \or \overline z \or w \or u \or \overline v) \and (\overline x \or \overline y \or z \or \overline w \or u \or v) \and (x \or \overline y \or \overline z \or w \or u \or \overline v)\and (x \or \overline y) }$

11.2. Draw the graph that results from the reduction of 3-SAT to vertex cover for the expression
$\displaystyle{ (x \or \overline y \or z) \and (\overline x \or y \or \overline z) \and(\overline x \or y \or z) \and (x \or \overline y \or \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.In the minimum element set cover problem, we seek a set cover $\displaystyle{ S \subseteq C }$ of a universal set $\displaystyle{ U = {1, . . . , n} }$ such that sum of the sizes of the subsets in $\displaystyle{ S }$ is at most $\displaystyle{ k }$.
(a) Show that $\displaystyle{ C = {{1, 2, 3}, {1, 3, 4}, {2, 3, 4}, {3, 4, 5}} }$ has a cover of size 6, but none of size 5 because of a repeated element.
(b) Prove that this problem is NP-hard. (Hint: set cover remains hard if all subsets are of the same size.)

11.14. The half-Hamiltonian cycle problem is, given a graph $\displaystyle{ G }$ with $\displaystyle{ n }$ vertices, determine whether $\displaystyle{ G }$ has a simple cycle of length exactly $\displaystyle{ [n/2] }$, where the floor function rounds its input down to the nearest integer. Prove that this problem is NP-hard.

11.15. The 3-phase power balance problem asks for a way to partition a set of n positive integers into three sets $\displaystyle{ A }$, $\displaystyle{ B }$, or $\displaystyle{ C }$ such that $\displaystyle{ \sum_{i} a_i = \sum_{i} b_i = \sum_{i} c_i }$. Prove that this problem is NP-hard using a reduction from integer partition or subset sum (see Section 10.5 (page 329)).

11.16. Show that the following problem is NP-complete:
• Problem: Dense subgraph
• Input: A graph $\displaystyle{ G }$, and integers $\displaystyle{ k }$ and $\displaystyle{ y }$.
• Output: Does $\displaystyle{ G }$ contain a subgraph with exactly $\displaystyle{ k }$ vertices and at least $\displaystyle{ y }$ edges?

11.17. Show that the following problem is NP-complete:
• Problem: Clique, no-clique
• Input: An undirected graph $\displaystyle{ G=(V,E) }$ and an integer $\displaystyle{ k }$.
• Output: Does $\displaystyle{ G }$ contain both a clique of size $\displaystyle{ k }$ and an independent set of size $\displaystyle{ k }$.

11.18. n Eulerian cycle is a tour that visits every edge in a graph exactly once. An Eulerian subgraph is a subset of the edges and vertices of a graph that has an Eulerian cycle. Prove that the problem of finding the number of edges in the largest Eulerian subgraph of a graph is NP-hard. (Hint: the Hamiltonian circuit problem is NP-hard even if each vertex in the graph is incident upon exactly three edges.)

11.19. Show that the following problem is NP-hard:
• Problem: Maximum Common Subgraph
• Input: Two graphs $\displaystyle{ G_1 = (V_1, E_1) }$ and $\displaystyle{ G_2 = (V_2, E_2) }$, and a budget $\displaystyle{ b }$.
• Output: Two sets of nodes $\displaystyle{ S_1 \subseteq V_1 }$ and $\displaystyle{ S_2 \subseteq V_2 }$ whose deletion leaves at least $\displaystyle{ b }$ nodes in each graph, and makes the two graphs identical.

11.20. A strongly independent set is a subset of vertices $\displaystyle{ S }$ in a graph $\displaystyle{ G }$ such that for any two vertices in $\displaystyle{ S }$, there is no path of length two in $\displaystyle{ G }$. Prove that strongly independent set is NP-hard.

11.21. A kite is a graph on an even number of vertices, say $\displaystyle{ 2n }$, in which $\displaystyle{ n }$ of the vertices form a clique and the remaining $\displaystyle{ n }$ vertices are connected in a tail that consists of a path joined to one of the vertices of the clique. Given a graph and a goal g, the max kite problem asks for a subgraph that is a kite and contains $\displaystyle{ 2g }$ nodes. Prove that max kite is NP-hard.

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