CS 21 Decidability and Tractability Winter 2024
Posted: February 28
Solution Set 6
If you have not yet turned in the Problem Set, you should not consult these solutions.
Copyright By PowCoder代写 加微信 powcoder
1. First, observe that subgroup isomorphism is in NP, because if we are given a specification of the subgraph of G and the mapping between its vertices and the vertices of H, we can verify in polynomial time that H is indeed isomorphic to the specified subgraph of G.
To show subgraph isomorphism is NP-hard, we reduce from clique. Given an instance (G,k) of clique, where G has n vertices, we produce the following instance of subgraph isomorphism: (G,H = Kl), where Kl is the complete graph on l vertices and l = min(k,n+ 1). This reduction runs in polynomial time.
If k > n, then (G,k) is a NO instance of clique and by our choice of l we produce a NO instance of subgraph isomorphism, since there can be no Kn+1 graph within G which has only n vertices.
Otherwise, it is clear that G contains a clique of size l = k if and only if G contains a subgraph isomorphic to H (these are just two ways of saying the same thing). Thus we have shown that subgraph isomorphism is NP-hard, as desired.
2. The problem is in NP because given T , it is easy to check whether each element of the universe U is in at least one set Si ∈ T. We reduce from vertex cover. Let ⟨G = (V,E),k⟩ be an instance of vertex cover. Our reduction produces an instance of set cover as follows: the universe is the set of edges E and for each vertex v ∈ V , we have a set Sv consisting of the edges incident to v in G. Clearly this reduction runs in polynomial time.
Now, we argue that “yes maps to yes”: if there is a vertex cover V′ ⊆ V with |V′| ≤ k, then thereisavertexcoverT ={Sv :v∈V′}ofsizeatmostkbydefinition(everyedgee=(u,v) has either u or v in V′ and either Sv or Su – both of which contain e – is therefore in T).
Wenowarguethat“nomapstono”: ifthereisasetcoverT with|T|≤k,thentakingV′ to be the set of vertices v such that Sv ∈ T, we obtain a vertex cover of size at most k (every edge e = (u,v) occurs in exactly two sets Sv and Su, and so one of them must be in T, and therefore one of u or v is in V′).
3. minimum bisection is in NP because given a set S ⊆ V (V are the vertices of the n node input graph) it is easy to verify that |S| = n/2 and count the number of edges crossing the cut, making sure there are at least k.
All of the graphs we discuss below are multigraphs (parallel edges allowed).
We reduce from max cut. Given an instance ⟨G = (V,E),k⟩ of max cut, we perform the following sequence of transformations. Let G1 be the graph G with an additional n isolated nodes. Observe that if there is a cut S ⊆ V in G with exactly l edges crossing it, there is a
bisection in G1 with exactly l edges crossing it, obtained by including n − |S| isolated nodes in the old cut. Also, if there is a bisection in G1 with exactly l edges crossing it, then by discarding the isolated nodes, we obtain a cut in G with exactly l edges crossing it.
Now let p be the maximum number of parallel edges occurring in G1. Define G2 to be the graph that has for each pair u ̸= v a number of parallel edges equal to p minus the number of parallel edges between u and v in G1. Observe that a bisection in G1 with exactly l edges crossing it, has exactly pn2 − l edges crossing it in G2. Similarly, a bisection in G2 with exactly l edges crossing it, has exactly pn2 − l edges crossing it in G1.
Finally, let G3 be the graph G2 with a clique on all of its 2|V | nodes added to the existing edges. This is clearly connected. Our reduction produces ⟨G3, pn2 + n2 − k⟩ and an instance of min bisection. Clearly this reduction runs in polynomial time.
Now for “yes maps to yes”. If there is a cut in G with at least k edges crossing it, then there is a bisection in G1 with at least k edges crossing it, and there is a bisection in G2 with at most pn2 − k edges crossing it as we have argued above. In G3, this cut has an additional n2 edges coming from the clique we added on top of G2 (there are n nodes on each side of the cut and all n2 edges between them are present in that clique). So we have a bisection with pn2 + n2 − k edges crossing it in G3 as required.
Finally we argue that “no maps to no”. Suppose there is a bisection in G3 with at most pn2 + n2 − k edges crossing it. We know that the clique we added to G3 contributes exactly n2 edges (because there are n nodes on each side of the cut and all n2 edges between them are present in that clique). So in G2 the same bisection has at most pn2 − k edges crossing it. As we argued above, this implies that G1 has at least k edges crossing it, and then (also as argued above) G must have a cut with at least k edges crossing it, as required.
(a) First, note that partition is in NP because given subset T ⊆ {1, 2, . . . , n} we can verify in polynomial time that Pi∈T ai = Pi̸∈T ai.
To show that partition is NP-hard, we reduce from subset sum. Given an instance (a1, a2, . . . , an, B) of subset sum, let M = Pi ai. Our reduction produces the following instance of partition:
a1,a2,…,an,an+1 =L−B,an+2 =L−(M−B)
where L = M + 1. Clearly this reduction runs in polynomial time.
If we started with a YES instance of subset sum, then we claim that the reduction produces a YES instance of partition. Suppose there exists a subset T ⊆ {1, 2, . . . , n} for which Pi∈T ai = B. Then we have Pi̸∈T ai = M−B, and so we have an+1+Pi∈T ai =
L = an+2 + Pa̸∈T ai, which implies that the instance is partitionable.
If the reduction produces a YES instance of partition, then we claim that (a1, a2, . . . , an, B) was a YES instance of subset sum. Let T′ specify the partition. Observe that we can’t have both an+1 and an+2 in the same part of the partition, because then the sum of the integers in that part would be at least an+1 +an+2 = 2L−M > M, and the sum of the integers in the other part would be at most M. The sum of all elements is 2L, so we must have:
X ai = L = X ai. i∈T ′ a̸∈T ′
If an+1 is in the first part, then T′ −{an+1} is a subset of elements of the subset sum instance that sum to B, and if an+1 is in the second part, then T′ −{an+1} is a subset of elements of S that sum to B. We conclude that we started with a YES instance of subset sum as required.
(b) First, note that knapsack is in NP because given subset of the n elements, we can verify in polynomial time that the sum of their values is at least V , and the sum of their costs is at most C.
To show that knapsack is NP-hard, we reduce from subset sum. Given an instance (S = {a1, a2, . . . , an}, B of subset sum, our reduction produces the following instance ofknapsack: thecostci ofitemiissettoai,andthevaluevi ofitemiissettoai as well. We set V = C = B. Clearly this reduction runs in polynomial time.
If we started with a YES instance of subset sum, then we claim that the reduction produces a YES instance of knapsack. Suppose there exists a subset T ⊆ S for which Pa∈T a = B. Then packing the element in T into our knapsack costs B and has value B, so the instance of knapsack produced by the reduction is a YES instance.
If the reduction produces a YES instance of knapsack, then we claim that (S,B) is a YES instance of subset sum. Let T ⊆ S be the items packed into the knapsack, whose total value is at least V and whose total cost is at most C. In other words Pa∈T a ≥ V = B and Pa∈T a ≤ C, which implies that Pa∈T a = B. We conclude that (S, B) is a YES instance of subset sum as required.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com