# 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.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.

### Creative Reductions

11.22. Prove that the following problem is NP-complete:
• Problem: Hitting Set
• Input: A collection ${\displaystyle C}$ of subsets of a set ${\displaystyle S}$, positive integer ${\displaystyle k}$.
• Output: Does ${\displaystyle S}$ contain a subset ${\displaystyle S'}$ such that ${\displaystyle |S'|\leq k}$ and each subset in ${\displaystyle C}$ contains at least one element from ${\displaystyle S'}$?

11.23. Prove that the following problem is NP-complete:
• Problem: Knapsack
• Input: A set ${\displaystyle S}$ of ${\displaystyle n}$ items, such that the ${\displaystyle i}$th item has value ${\displaystyle v_{i}}$ and weight ${\displaystyle w_{i}}$. Two positive integers: weight limit ${\displaystyle W}$ and value requirement ${\displaystyle V}$.
• Output: Does there exist a subset ${\displaystyle S'\in S}$ such that ${\displaystyle \sum _{i\in S'}w_{i}\leq W}$ and ${\displaystyle \sum _{i\in S'}v_{i}\geq V}$?
(Hint: start from integer partition.)

11.24. Prove that the following problem is NP-complete:
• Problem: Hamiltonian Path
• Input: A graph ${\displaystyle G}$, and vertices ${\displaystyle s}$ and ${\displaystyle t}$.
• Output: Does ${\displaystyle G}$ contain a path which starts from ${\displaystyle s}$, ends at ${\displaystyle t}$, and visits all vertices without visiting any vertex more than once? (Hint: start from Hamiltonian cycle.)

11.25. Prove that the following problem is NP-complete:
• Problem: Longest Path
• Input: A graph ${\displaystyle G}$ and positive integer ${\displaystyle k}$.
• Output: Does ${\displaystyle G}$ contain a path that visits at least ${\displaystyle k}$ different vertices without visiting any vertex more than once?

11.26. Prove that the following problem is NP-complete:
• Problem: Dominating Set
• Input: A graph ${\displaystyle G=(V,E)}$ and positive integer ${\displaystyle k}$.
• Output: Is there a subset ${\displaystyle V'\in V}$ such that ${\displaystyle |V'|\leq k}$ where for each vertex ${\displaystyle x\in V}$ either ${\displaystyle x\in V'}$ or there exists an edge ${\displaystyle (x,y)}$, where ${\displaystyle y\in V'}$.

11.27. Prove that the vertex cover problem (does there exist a subset ${\displaystyle S}$ of ${\displaystyle k}$ vertices in a graph ${\displaystyle G}$ such that every edge in ${\displaystyle G}$ is incident upon at least one vertex in ${\displaystyle S}$?) remains NP-complete even when all the vertices in the graph are restricted to have even degrees.

11.28. Prove that the following problem is NP-complete:
• Problem: Set Packing
• Input: A collection ${\displaystyle C}$ of subsets of a set ${\displaystyle S}$, positive integer ${\displaystyle k}$.
• Output: Does ${\displaystyle S}$ contain at least ${\displaystyle k}$ disjoint subsets (i.e., such that none of these subsets have any elements in common?)

11.29. Prove that the following problem is NP-complete:
• Problem: Feedback Vertex Set
• Input: A directed graph ${\displaystyle G=(V,A)}$ and positive integer ${\displaystyle k}$.
• Output: Is there a subset ${\displaystyle V'\in V}$ such that ${\displaystyle |V'|\leq k}$, such that deleting the vertices of ${\displaystyle V'}$ from ${\displaystyle G}$ leaves a DAG?

11.30. Give a reduction from Sudoku to the vertex coloring problem in graphs. Specifically, describe how to take any partially filled Sudoku board and construct a graph that can be colored with nine colors iff the Sudoku board is solvable.

### Algorithms for Special Cases

11.31

11.32

11.33

11.34

11.35

Back to Chapter List