CS 21 Decidability and Tractability Winter 2024
Out: February 21
Due: February 28
Problem Set 6
Copyright By PowCoder代写 加微信 powcoder
Reminder: you are encouraged to work in groups of two or three; however you must turn in your own write-up and note with whom you worked. You may consult the course notes and the text (Sipser). The full honor code guidelines and collaboration policy can be found in the course syllabus.
Please attempt all problems. Please select one the first two problems to be graded completely (and indicate clearly which one); the other one will receive 1 point for a credible attempt. Please turn in your solutions via Gradescope, by 1pm on the due date.
1. Recall that two graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic if there is a bijection f : V1 → V2 such that (u,v) ∈ E1 ⇔ (f(u),f(v)) ∈ E2. On the Problem Set 4 you showed that containsH is in P.
Prove that the following variation in which H is part of the input is NP-complete: subgraph isomorphism = {(G,H) : G contains a subgraph isomorphic to H}.
As in the previous problem set, by “subgraph” we mean a subset of G’s vertices together with all of G’s edges on that subset of vertices. A side note: the related problem
graph isomorphism = {(G,H) : G is isomorphic to H} is not know to be NP-complete, nor is it known to be in P.
2. Let C = {S1,S2,S3,…,Sn} be a collection of sets and define U = ∪iSi. We say that T ⊆ C is a cover if every u ∈ U occurs in at least one Si ∈ T . Prove that the language:
set cover = {(C,k) : there is a cover T ⊆ C with |T| ≤ k}.
is NP-complete.
3. AcutofanundirectedgraphG=(V,E)isasubsetofverticesS⊆V. Wesaythatanedge crosses the cut if one endpoint is in S and the other is in V \ S. In class, we will show that the following language is NP-complete:
maxcut = {(G = (V,E),k) : there is a cut S ⊆ V with at least k edges crossing it.
In this problem you will consider a related problem concerning special cuts called bisections. A bisection of a graph G = (V,E) is a cut S ⊆ V with |S| = |V|/2. A powerful and general algorithmic strategy is to represent the “components” of a problem by vertices of a graph G and dependencies between components by its edges; then a bisection splits the problem into two equal pieces, which can be solved recursively and merged to produce a global solution. In this general framework, the work in the merging step often depends on the number of
edges crossing the bisection. Thus, one might hope to be able to efficiently solve the following problem, minimum bisection:
{(G, k) : G is a connected multigraph having a bisection with at most k edges crossing it.} Unfortunately, an efficient solution is unlikely. Prove that min bisection is NP-complete.
Hint: what is the relationship between this problem and the maximization version, maximum bisection:
{(G, k) : G is a connected multigraph having a bisection with at least k edges crossing it.}? 4. In class we will show that the following problem concerning positive integers is NP-complete:
() subset−sum= (a1,a2,…,an,B):∃S⊆[n]forwhich Xai =B.
i∈S This will be useful when giving reductions for the following problems:
(a) Alistofpositiveintegers(a1,a2,…,an)ispartitionableifthereisasubsetT ⊆{1,2,…,n} for which Pi∈T ai = Pi̸∈T ai. Show that the following language is NP-complete:
partition = {S = (a1, a2, . . . , an) : S is partitionable}
(b) In the “knapsack problem” we are given n items each of which has a positive integer cost ci and a positive integer value vi. We are asked to pack a knapsack with items whose total value is at least V , and without exceeding a budget C. Show that the following language is NP-complete:
knapsack = {(c1,c2,…,cn,v1,v2,…,vn,V,C) : ∃ T ⊆ {1,2,…,n}
forwhich Xvt ≥V and Xct ≤C} t∈T t∈T
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com