question archive Consider the following two problems: (a) Traveling Salesman Problem (TSP): Input: n cities with distances between every pair of cities
Consider the following two problems: (a) Traveling Salesman Problem (TSP): Input: n cities with distances between every pair of cities
Subject:Computer SciencePrice: Bought3
Consider the following two problems:
(a) Traveling Salesman Problem (TSP):
Input: n cities with distances between every pair of cities.
Problem: Starting from a city c, is there a way to visit every other city and come back to c such that the total distance traveled is at most D?
(b) Clique:
Input: An undirected graph G = (V, E) and an integer k > 0.
Problem: Is there a subset S ⊆ V such that |S| ≥ k and there is an edge between every pair of vertices in S?
a. (5 points) Show that each of the above problems is in NP (Hint: describe 'short' witness for the "yes" instances):
b. (5 points) The above problems are in fact NP-complete problems. For each of the them, give a brute-force algorithm to solve them. What is the running time of the your algorithm?
