CSCI 570 Homework 11
Due November 27th
1 Graded Problems
1. In the clique problem, we are given an undirected graph G = (V, E) and an integer k, the problem is to decide whether there exists a subset V ⊆ V,|V| ≥ k such that for any u, v ∈ V (u ̸= v), (u, v) ∈ E. Prove that clique is NP-complete using a reduction from independent set.
2. In the subset sum problem, we are given a set of integers D and an integer S. The goal is to decide whether there exists D ⊆ D such that = S.
d∈D Prove that subset sum is NP-complete using a reduction from 3-sat.
3. Suppose that you are traveling to Paris. The city is defined as a directed graph G = (V,E) and each edge e ∈ E is associated with a non-negative cost ce. Your hotel is located at s ∈ V. There is a set of landmarks X ⊆ V where you want to visit. You want to find a set of edges F such F contains a directed path from s to each vertex in X. Due to limited budget, you wonder whether there exists a F with total costs ≤ k. Prove that this problem is NP-complete using a reduction from 3-sat.
2 Practice Problems
1. Kleinberg and Tardos, 8.27. 2. Kleinberg and Tardos, 8.5.
1