Prove this is NP Complete, or it is in P. 
Homework Answers
for the proof of Np-completeness we first show it belong to NP by certificate
certifiacte is the set of N vertices
now A problem is said to be in Np is if a solution verified in polynomial time.
in our case praposed solution is list of vetices
to check the solution 1 check all vertices are there or not and vertices are connected by an edge and last vertices are connected to 1 by an edge
so this give us order of n because there are n vertices and we have to check n edges so this can be done in polynomial time
Add Answer to:
Prove this is NP Complete, or it is in P.
This problem is a variant of...
Problem 3: Bounded-Degree Spanning Trees (10 points). Recall the minimum spanning tree problem studied in class....
Problem 3: Bounded-Degree Spanning Trees (10 points). Recall the minimum spanning tree problem studied in class. We define a variant of the problem in which we are no longer concerned with the total cost of the spanning tree, but rather with the maximum degree of any vertex in the tree. Formally, given an undirected graph G = (V,E) and T ⊆ E, we say T is a k-degree spanning tree of G if T is a spanning tree of G,...
Prove that the following problem is NP-complete: given an undirected graph G = (V, E) and...
Prove that the following problem is NP-complete: given an undirected graph G = (V, E) and an integer k, return a clique of size k as well as an independent set of size k, provided both exist.
Problem 3: Suppose you are given an undirected graph G and a specified starting node s...
Problem 3: Suppose you are given an undirected graph G and a specified starting node s and ending node t. The HaMILTONIAN PATH problem asks whether G contains a path beginning at s and ending at t that touches every node exactly once. The HAMILTONIAN CYCLE problem asks whether con- tains a cycle that touches every node exactly once (cycles don't have starting or ending points, so s and t are not used here) Assume that HaMIlTonian CYCLe is NP-Complete....
Note: For the following problems, you can assume that INDEPENDENT SET, VERTEX COVER, 3-SAT, HAMILTONIAN PATH, and GRAPH COLORING are NP-complete. You, of course, may look up the defini- tions of the...
Note: For the following problems, you can assume that INDEPENDENT SET, VERTEX COVER, 3-SAT, HAMILTONIAN PATH, and GRAPH COLORING are NP-complete. You, of course, may look up the defini- tions of the above problems online. 5. The LONGEST PATH problem asks, given an undirected graph G (V, E), and a positive integer k , does G contain a simple path (a path visiting no vertex more than once) with k or more edges? Prove that LONGEST PATH is NP-complete.
Note:...
Problem 5. (Lexicographical Optimisation with Paths) Provide pseudocode and an expla- nation for an algorithm that comp...
Problem 5. (Lexicographical Optimisation with Paths) Provide pseudocode and an expla- nation for an algorithm that computes a path between two nodes in an undirected graph such that: . The maximum weight in the path is minimised, ie., there does not exist another path with a smaller maximum weight .Amongst all such paths, it finds the path with minimum cost. . The time complexity is no worse than 0(( and V is the set of nodes. ·IvD-log(IVD), where E is...
the definitions are below x is any input to the program 1. Show that Lacc is...
the definitions are below
x is any input to the program
1. Show that Lacc is NP-Hard. * * * * Recall: NP = the class of efficiently verifiable languages. * The set of all languages that can be verified in polynomial time. * Examples: * MAZE = {(G,s,t): G is a graph. There is a path s->t in G}. * HAMCYCLE = {G:G is an undirected graph with a Hamiltonian Cycle} * COMPOSITES = {n EN:n= pq for some...
Note that things like searching for solutions online is still prohibited In order to prove a...
Note that things like searching for solutions online is still prohibited In order to prove a problem is NP-complete, you must: . Show that the problem is in NP. .A reduction in the correct direction. Reductions in the wrong direction will considerably reduce the credit you can get for a problem . An explanation for why your reduction has no false positives. An explanation for why your reduction has no false negatives. You may assume that any problem shown to...
true or False with prove? (f) ___ NP =co-NP (g) The complement of any recursive language...
true or False with prove?
(f) ___ NP =co-NP (g) The complement of any recursive language is recursive. h) The grader's problem is decidable. We say programs Pi and P are equivalent if they give the same output if given the same input. The problem is to decide whether two programs (in C++, Pascal, Java, or some other modern programming language) are equivalent. )Given any CF language L, there is always an unambiguous CF grammar which generates L 6)Given any...
4. Approximating Clique. The Maximum Clique problem is to compute a clique (i.e., a complete subgraph) of maximum size i...
4. Approximating Clique. The Maximum Clique problem is to compute a clique (i.e., a complete subgraph) of maximum size in a given undirected graph G. Let G = (V,E) be an undirected graph. For any integer k ≥ 1, define G(k) to be the undirected graph (V (k), E(k)), where V (k) is the set of all ordered k-tuples of vertices from V , and E(k) is defined so that (v1,v2,...,vk) is adjacent to (w1,w2,...,wk) if and only if, for...
3. (3 pts) Two well-known NP-complete problems are 3-SAT and TSP, the traveling salesman problem. The...
3. (3 pts) Two well-known NP-complete problems are 3-SAT and TSP, the traveling salesman problem. The 2-SAT problem is a SAT variant in which each clause contains at most two literals. 2-SAT is known to have a polynomial-time algorithm. Is each of the following statements true or false? Justify your answer. a. 3-SAT sp TSP. b. If P NP, then 3-SAT Sp 2-SAT. C. If P NP, then no NP-complete problem can be solved in polynomial time.
Problem 3: Suppose you are given an undirected graph G and a specified starting node s and ending node t. The HaMILTONIAN PATH problem asks whether G contains a path beginning at s and ending at t that touches every node exactly once. The HAMILTONIAN CYCLE problem asks whether con- tains a cycle that touches every node exactly once (cycles don't have starting or ending points, so s and t are not used here) Assume that HaMIlTonian CYCLe is NP-Complete....
Note: For the following problems, you can assume that INDEPENDENT SET, VERTEX COVER, 3-SAT, HAMILTONIAN PATH, and GRAPH COLORING are NP-complete. You, of course, may look up the defini- tions of the above problems online. 5. The LONGEST PATH problem asks, given an undirected graph G (V, E), and a positive integer k , does G contain a simple path (a path visiting no vertex more than once) with k or more edges? Prove that LONGEST PATH is NP-complete.
Note:...
Problem 5. (Lexicographical Optimisation with Paths) Provide pseudocode and an expla- nation for an algorithm that computes a path between two nodes in an undirected graph such that: . The maximum weight in the path is minimised, ie., there does not exist another path with a smaller maximum weight .Amongst all such paths, it finds the path with minimum cost. . The time complexity is no worse than 0(( and V is the set of nodes. ·IvD-log(IVD), where E is...
the definitions are below
x is any input to the program
1. Show that Lacc is NP-Hard. * * * * Recall: NP = the class of efficiently verifiable languages. * The set of all languages that can be verified in polynomial time. * Examples: * MAZE = {(G,s,t): G is a graph. There is a path s->t in G}. * HAMCYCLE = {G:G is an undirected graph with a Hamiltonian Cycle} * COMPOSITES = {n EN:n= pq for some...
Note that things like searching for solutions online is still prohibited In order to prove a problem is NP-complete, you must: . Show that the problem is in NP. .A reduction in the correct direction. Reductions in the wrong direction will considerably reduce the credit you can get for a problem . An explanation for why your reduction has no false positives. An explanation for why your reduction has no false negatives. You may assume that any problem shown to...
true or False with prove?
(f) ___ NP =co-NP (g) The complement of any recursive language is recursive. h) The grader's problem is decidable. We say programs Pi and P are equivalent if they give the same output if given the same input. The problem is to decide whether two programs (in C++, Pascal, Java, or some other modern programming language) are equivalent. )Given any CF language L, there is always an unambiguous CF grammar which generates L 6)Given any...
3. (3 pts) Two well-known NP-complete problems are 3-SAT and TSP, the traveling salesman problem. The 2-SAT problem is a SAT variant in which each clause contains at most two literals. 2-SAT is known to have a polynomial-time algorithm. Is each of the following statements true or false? Justify your answer. a. 3-SAT sp TSP. b. If P NP, then 3-SAT Sp 2-SAT. C. If P NP, then no NP-complete problem can be solved in polynomial time.
Most questions answered within 3 hours.
-
Write a program to solve the Josephus problem, with the following
modification:
Sample Input:
./a.out n...
asked 47 minutes ago -
At the start of a CD it is spinning at a rate of 525 rpm
(revolutions...
asked 1 hour ago -
4. Without doing any calculations, predict whether the observed
∆T would increase, decrease or remain the...
asked 2 hours ago -
Based on the range, which of the following sets of scores has
the greatest variability? 3,...
asked 3 hours ago -
Ripples in a pond travel at a velocity of 3 m/s with one peak
passing a...
asked 3 hours ago -
A man stands on the roof of a building of height 13.0 mm and
throws a...
asked 3 hours ago -
The extent to which assets are financed by borrowed funds and
other liabilities is indicated by:...
asked 4 hours ago -
Explain in detail
Germany is the fifth largest economy
explain what goods and services Germany specializes...
asked 4 hours ago -
The density of platinum is 21.45 g/mL. If a cube of platinum
with a mass of...
asked 5 hours ago -
Accounts Receivable
Sales
A/R Posting
Extended Sales Invoice
Packing Slip
Compare invoice to packing slip 2...
asked 5 hours ago -
Michaella, age 23, is a full-time law student and is claimed by
her parents as a...
asked 5 hours ago -
Why are polymers not typically casted into products?
asked 5 hours ago