The subgraph-isomorphism problem takes two undirected graphs
$G_1$ and$G_2$ , and it asks whether$G_1$ is isomorphic to a subgraph of$G_2$ . Show that the subgraphisomorphism problem is$\text{NP-complete}$ .
(Omit!)
Given an integer
$m \times n$ matrix$A$ and an integer$m$ -vector$b$ , the 0-1 integerprogramming problem asks whether there exists an integer$n$ -vector$x$ with elements in the set$\{0, 1\}$ such that$Ax \le b$ . Prove that 0-1 integer programming is$\text{NP-complete}$ . ($\textit{Hint:}$ Reduce from$\text{3-CNF-SAT}$ .)
(Omit!)
The integer linear-programming problem is like the 0-1 integer-programming problem given in Exercise 34.5-2, except that the values of the vector
$x$ may be any integers rather than just$0$ or$1$ . Assuming that the 0-1 integer-programming problem is$\text{NP-hard}$ , show that the integer linear-programming problem is$\text{NP-complete}$ .
(Omit!)
Show how to solve the subset-sum problem in polynomial time if the target value
$t$ is expressed in unary.
(Omit!)
The set-partition problem takes as input a set
$S$ of numbers. The question is whether the numbers can be partitioned into two sets$A$ and$\bar A = S - A$ such that$\sum_{x \in A} x = \sum_{x \in \bar A} x$ . Show that the set-partition problem is$\text{NP-complete}$ .
(Omit!)
Show that the hamiltonian-path problem is
$\text{NP-complete}$ .
(Omit!)
The longest-simple-cycle problem is the problem of determining a simple cycle (no repeated vertices) of maximum length in a graph. Formulate a related decision problem, and show that the decision problem is
$\text{NP-complete}$ .
(Omit!)
In the half 3-CNF satisfiability problem, we are given a
$\text{3-CNF}$ formula$\phi$ with$n$ variables and$m$ clauses, where$m$ is even. We wish to determine whether there exists a truth assignment to the variables of$\phi$ such that exactly half the clauses evaluate to$0$ and exactly half the clauses evaluate to$1$ . Prove that the half$\text{3-CNF}$ satisfiability problem is$\text{NP-complete}$ .
(Omit!)