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

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用