CSCI 570 Homework 11 Solution
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.
Solution:
1. clique ∈ NP. Given V, we can check whether |V| ≥ k and for any u,v ∈ V(u ̸= v), (u,v) ∈ E. If so, we output “yes” and otherwise “no”. This verifica- tion takes a polynomial running time of O(V + E).
2. independent-set ≤p clique. We use a reduction function f that takes (G, k) and outputs (G, k), where G is the complement graph of G. This reduc- tion takes a polynomial running time of O(V + E).
To establish the correctness of our reduction, we need to show that G has an independent set of size k′ ≥ k if and only if G has an clique of size k′ ≥ k.
(a) (⇒) If G has an independent set V and |V| ≥ k, by the definition of inde- pendent set, ∀u,v ∈ V(u ̸= v), (u,v) ∈/ E. Then in the complement graph G, ∀u,v∈V(u̸=v),(u,v)∈E,soV isacliqueofgraphGand|V|≥k. (b)(⇐)IfGhasancliqueV and|V|≥k,∀u,v∈V(u̸=v),(u,v)∈E. Then in G, ∀u,v ∈ V(u ̸= v), (u,v) ∈/ E, so V is an independent set of graph G and | V | ≥ k .
(a) and (b) prove the correctness of our reduction. Since independent-set ≤p clique and clique ∈ NP, clique is NP-complete.
Graded Problem 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 that subset sum is NP-complete using a reduction from 3-sat.
Solution: Refer to section 8.8 of Kleinberg and Tardos.
1
= S. Prove
d∈D
Graded Problems 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.
Solution:
1. This problem is in NP. Given F, we can delete all edges ∈/ F and run BFS (or DFS) from s, then check whether every vertex in X is reachable. We also need to check whether the total costs of edges in F ≤ k. We output “yes” if F passes both tests and otherwise “no”. This verification can be done in a polynomial time of O(|V | + |E|).
2. This problem is in NP-hard. We prove it using a reduction from 3-sat. Assume the 3-SAT problem consists of n variables and m clauses. We construct a graph containing:
• Nodes: 2n literal nodes {xi}ni=1 and {xi}ni=1, m clause nodes {cj}mj=1, n variable nodes {vk}nk=1, one source node s. This graph contains 3n + m nodesintotal.WesetX={vk}nk=1∪{cj}mj=1 andthehoteltos.
• Edges: 2n edges with cost 1 between s and each literal nodes; n edges with cost 1 between xi and vi; n edges with cost 1 between xi and vi; edges with cost 1 between xi (or xi) and cj if cj contains the literal xi (or xi). This graph contains 4n + 3m edges in total.
This reduction takes O(m + n) and is therefore polynomial. To establish the correctness of our reduction, we need to prove that 3-SAT is satisfiable if and only if the constructed graph has an F with costs ≤ 2n + m.
(a) (⇒) If 3-SAT is satisfiable, we can find an F that satisfies our requirements. Specifically, we choose edges (s, xi), (xi, vi) if the ith variable is true and choose the edges (s, xi), (xi, vi) if the ith variable is false. This make all vi, i = 1, …, n reachable from s. Then for each clause c, since it contains at least one true literal (say x), the edge (s,x) must have been chosen in the previous step, so we can choose (x, c) and every clause node is also reachable from s. All chosen edges constitute an edge set F that makes all nodes in X reachable from s and the total edge costs is exactly 2n + m.
(b) (⇐) If there exists an F that satisfies all requirements, then the 3-SAT problem must be satisfiable. For each node u in X, we need at least one edge that points to u. Since |X| = m + n, we need at least m + n edges. Also, since vi is only connected to xi and xi , we need at least one edge in {(s, xi ), (s, xi )}. Therefore, we need another n edges and the total number of edges should be at least 2n+m. Then 2n+m ≤ |F| ≤ 2n+m and thus F contains exactly 2n + m edges. We assign the ith variable to true if (s, xi ) ∈ F and otherwise
2
false. We then prove that this assignment is feasible. First, as we don’t choose both (s,xi) and (s,xi), this assignment is legal. Besides, as all clause nodes are reachable, there must be at least one true literal in each clause.
(a) and (b) prove the correctness of our reduction. Since the problem is in both NP and NP-hard, this problem is NP-complete.
Practice Problem 1
1. This problem is in NP. We can calculate the squared sum of subsets and check whether the sum ≤ B, this verification takes a polynomial running time of O(k).
2. partition ≤p this problem, which is a decision problem of whether a set S can be partitioned into S1 and S2 such that x∈S1 x = x∈S2 x. We can set
xi
i ,
2 2 s∈S1 x+s∈S2 x2
B≥ x + x ≥ 2 =B,
(x∈S s)2 2
.
(⇒) If the partitioning problem has a solution, sum of S1 = sum of S2 =
k = 2 and B =
( xi)2 then B = i .
2 2 2 (x∈S x)2
2
(⇐)IfthereexistsS1 andS2 suchthat s∈S1 x + x∈S2 x = 2 ,
since
s∈S1 x∈S2
the equality holds, and we have s∈S1 x = x∈S2 x (by QM-AM inequality).
Then the partition problem has a solution. Our reduction is correct.
Since this problem is both NP and is reducible to partition, this problem is NP-complete.
Practice Problem 2
1. hitting set ∈ NP. Given a set H, we can check whether |H| ≤ k and whether H contains at least one member from each Bi. This verification takes a polynomial running time.
2. hitting set is NP-hard. We prove it using a reduction from vertex cover. Given an instance of vertex cover, specified by G = (V,E) and k, we let A = V and construct B = {u,v} for each (u,v) ∈ E. This reduction takes polynomial time. To establish the correctness of our reduction, we need to prove that the graph G contains a vertex cover with ≤ k nodes if and only if there is a hitting set H ⊆ A and |H| ≤ k.
(⇒) If we have a vertex cover C ⊆ V (|C| ≤ k), for each set B = {u, v}, at least one node from u, v must ∈ C. Therefore, we can take C as the hitting set. (⇐) If we have a hitting set H(|H| ≤ k), for each edge e = (u, v), at least one node from u,v must ∈ H. Thus we can take H as the vertex cover. So our
3
reduction is correct. Since hitting set is both in NP and NP-hard, hitting set is NP-complete.
4