34.5 NP-complete problems

34.5-1

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!)

34.5-2

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!)

34.5-3

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!)

34.5-4

Show how to solve the subset-sum problem in polynomial time if the target value $t$ is expressed in unary.

(Omit!)

34.5-5

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!)

34.5-6

Show that the hamiltonian-path problem is $\text{NP-complete}$.

(Omit!)

34.5-7

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!)

34.5-8

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!)