91影视

Determine which of the following problems are NP-complete and which are solvable in polynomial time. In each problem you are given an undirected graph $\mathbf{G}\mathbf{=}\mathbf{(}\mathbf{V}\mathbf{,}\mathbf{E}\mathbf{)}$, along with:

(a)A set of nodes$\mathbf{L}\mathbf{鈯�}\mathbf{V}$ , and you must find a spanning tree such that its set of leaves includes the set $\mathbf{L}$.

(b)A set of nodes $\mathbf{L}\mathbf{鈯�}\mathbf{V}$, and you must find a spanning tree such that its set of leaves is precisely the set $\mathbf{L}$.

(c)A set of nodes$\mathbf{L}\mathbf{鈯�}\mathbf{V}$ , and you must find a spanning tree such that its set of leaves is included in the set $\mathbf{L}$.

(d)An integer $\mathbf{k}$, and you must find a spanning tree with$\mathbf{k}$ or fewer leaves.

(e)An integer $\mathbf{k}$, and you must find a spanning tree with$\mathbf{k}$ or more leaves.

(f)An integer $\mathbf{k}$, and you must find a spanning tree with exactly$\mathbf{k}$ leaves.

Prove that the following problem is NP-complete: given an undirected graph

$G=\left(V,E\right)$and an integer $k$, return a clique of size $k$as well as an independent set of size $k$, provided both exist.

Akiteis a graph on an even number of vertices, say 2n, in which of the vertices form a clique and the remaining vertices are connected in a 鈥渢ail鈥� that consists of a path joined to one of the vertices of the clique. Given a graph and a goal , the KITE problem asks for a subgraph which is a kite and which contains 2g nodes. Prove that KITE is NP-complete.

Optimization versus search.Recall the traveling salesman problem:

TSP

Input: A matrix of distances; a budget b

Output: A tour which passes through all the cities and has $\mathbf{\text{length}}\mathbf{鈮�}\mathit{b}$, if such a tour exists.

The optimization version of this problem asks directly for the shortest tour.

TSP-OPT

Input:A matrix of distances

Output:The shortest tour which passes through all the cities.

Show that if TSP can be solved in polynomial time, then so can TSP-OPT.

STINGY SAT is the following problem: given a set of clauses (each a disjunction of literals) and an integer K , find a satisfying assignment in which at most K variables are true, if such an assignment exists. Prove that is$\mathbf{NP}$ -complete.

Consider the CLIQUE problem restricted to graphs in which every vertex has degree at most v. Call this problem CLIQUE-3 .

(a) Prove that CLIQUE-3 is in NP .

(b) What is wrong with the following proof of NP-completeness for CLIQUE-3 ? We know that the CLIQUE problem in general graphs is NP-complete, so it is enough to present a reduction from CLIQUE-3 to CLIQUE . Given a graph G with vertices of degree $\mathbf{鈮�}\mathbf{3}$, and a parameter g, the reduction leaves the graph and the parameter unchanged: clearly the output of the reduction is a possible input for the CLIQUE problem. Furthermore, the answer to both problems is identical. This proves the correctness of the reduction and, therefore, the NP-completeness of CLIQUE-3 .

(c) It is true that the VERTEX COVER problem remains NP-complete even when restricted to graphs in which every vertex has degree at most 3 . Call this problem VC-3 . What is wrong with the following proof of NP-completeness for CLIQUE ? We present a reduction from VC-3 to CLIQUE-3 . Given a graph G=(V,E) with node degrees bounded by 3 , and a parameter b , we create an instance of CLIQUE-3 by leaving the graph unchanged and switching the parameter to $\left|V\right|\mathbf{-}\mathbf{b}$. Now, a subset $\mathit{C}\mathbf{鈯�}\mathit{V}$is a vertex cover in G if and only if the complementary set V-C is a clique in G. Therefore G has a vertex cover of $\mathbf{size}\mathbf{鈮�}\mathbf{b}$if and only if it has a clique of size $\mathbf{鈮�}\left|V\right|\mathbf{-}\mathbf{b}$. This proves the correctness of the reduction and, consequently, the NP-completeness of CLIQUE-3 .

(4)Describe an $\mathbf{O}\left(\left|V\right|\right)$algorithm for CLIQUE-3 .

On page $\mathbf{266}$we saw that 3SATremainsNP-complete even when restricted to formulas in which each literal appears at most twice.

(a)Show that if each literal appears at mostonce,then the problem is solvable in polynomial time.

(b)Show that INDEPENDENT SET remains NP-complete even in the special case when all the nodes in the graph have degree at most $\mathbf{4}$.