2. True or False: and explain why. (Ch 12 NP - Completeness) d. Suppose the clique problem is polynomially reducible to the vertex-cover problem. If the vertex-cover problem is in P, then the clique problem is also in P. e. If a problem is shown to be NP-Complete, it is likely that it is not in P. f. The worst-case running time of a non-deterministic computation looks at the height of its computation tree. g. All the NP-complete problems are known to be reducible to one another

2. True or False: and explain why. (Ch 12 NP - Completeness) d. Suppose the clique problem is polynomially reducible to the vertex-cover problem. If the vertex-cover problem is in P, then the clique problem is also in P. e. If a problem is shown to be NP-Complete, it is likely that it is not in P. f. The worst-case running time of a non-deterministic computation looks at the height of its computation tree. g. All the NP-complete problems are known to be reducible to one another

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

True or False: and explain why. (CH12 NP-Completeness) a. It is known that PC NP. b. If a decision problem is hard, the corresponding optimization problem is also hard. C. The Traveling salesperson problem is known to be not in P. d. Suppose the clique problem is polynomially reducible to the vertex-cover problem. If the vertex-cover problem is in P, then the clique problem is also in P. e. If a problem is shown to be NP-Complete, it is likely that it is not in P. f. The worst-case running time of a non-deterministic computation looks at the height of its computation tree. g. All the NP-complete problems are known to be reducible to one another
Provide evidence that the modified version of the choice problem has an NP-complete solution; Exists, given a graph G and a target cost c, a spanning tree in which the highest possible payment at any vertex does not exceed the target cost?
The graph-coloring problem is usually stated as the vertex-coloring problem: assign the smallest number of colors to vertices of a given graph so that no two adjacent vertices are the same color. Consider the edge-coloring problem: assign the smallest number of colors possible to edges of a given graph so that no two edges with the same end point are the same color. Explain how the edge-coloring problem can be polynomial reduced to a vertex-coloring problem. Give an example.
Suppose the clique problem is polynomially reducible to the vertex-cover problem. If the clique problem is in P, then the vertex-cover problem is also in P. True False All the NP-complete problems are known to be reducible to one another. True False
The graph five-coloring problem is stated as follows: Determine if the vertices of G can be colored using 5 colors such that no two adjacent vertices share the same color. Prove that the five-coloring problem is NP-complete. Hint: You can assume that graph 3-coloring is NP-complete
(c) You are given a directed graph G where all edge weights are positive. Given two vertices s and t in G, we want to find the "best" path from s to t, where "best" means the primary objective is to minimise the total weight of all edges along the path; if there are multiple paths with the same minimum weight, we prefer the one with the fewest edges. i. Write down the pseudocode of an efficient algorithm for this problem. You only need to compute the total weight and the number of edges of the best path, and need not recover the path itself. ii. Demonstrate how your algorithm works with the graph G2 in Figure 1. You should show the contents of any data structure used after each step. a b. 14 7 2 9 3 10 8 Of 12 11 6. 5 1 13 H G, Figure 1: G1 for Q3(a); H for Q3(b); G2 for Q3(c).
Prove that the following problem is NP-complete: Given a graph G, and an integer k, find whether or not graph G has a spanning degree where the maximum degree of any node is k. (Hint: Show a reduction from one of the following known NP-complete problems: Vertex Cover, Ham Path or SAT.)
Write the linear program (variable list, objective function and constraints) for the vertex cover problem .of fallowing graph A B D E H F
Problem 3: The VERTEX COVER problem is as follows: Given a graph G and some value c, is there a set of c vertices in the graph such that every edge in the graph is adjacent to at least one of those c vertices (in other words, every edge must have at least one of its two endpoints included in the set of c vertices)? VERTEX COVER is known to be NP-Complete.
3) The graph k-coloring problem is stated as follows: Given an undirected graph G = (V,E) with N vertices and M edges and an integer k. Assign to each vertex v in Va color c(v) such that 1< c(v)
5. Consider the following modification of the independent set problem. As input, you receive an undirected graph G = (V, E). As output, you must decide if G contains an independent set UCV such that U contains at least 99% of the vertices in V (that is, JU| > 0.99|V|). Prove that this modification of the independent set problem is NP-Complete.
Showing that a problem is NP complete requires Polynomial-time Reduction. Now, a set of nodes "V" is a vertex cover. The removal of V from the graph destroys every edge. This is the VERTEX_COVER problem. In the graph shown below in Fig. 1, {A, C, D, F} is a vertex cover. Given the input as the graph G and an integer k, does there exist a vertex_cover of G at most k nodes? Explain then, how you can use 3SAT (using two connected nodes for each variable and three connected nodes for each clause) for showing that vertex_cover problem is NP complete. You w m ooin m can be creative in your explanation. D B E