CS/ECE 374 A (Spring 2022) Homework 11 Solutions
Problem 11.1: Consider the following problem Colorful-Walk (which is an extension of Prob- lem 8.2(b) from HW8):
Input: a directed graph G = (V,E) with n vertices and m edges, a vertex s ∈ V, and a color c(e) ∈ {1,…,k} for each edge e ∈ E, and a number l.
Output: “yes” iff there exists a walk that starts at s and encounters at least l distinct colors.
Copyright By PowCoder代写 加微信 powcoder
Consider the Set-Cover problem:
Input: a set X of N elements, a collection of M subsets S = {S1,…,SM} where each Si ⊆ X, and a number K.
Output: “yes” iff there exists a subcollection T ⊆ S of K subsets, such that the union of the subsets in T includes all elements of X.
Describe a polynomial-time reduction from Set-Cover to Colorful-Walk. Follow these steps:
Given an input to Set-Cover (i.e., X, S, and K), describe a construction of an input to Colorful-Walk (i.e., G, s, c(·), and l). Check that your construction takes polynomial time.
Prove that the input to Set-Cover has a “yes” answer if and only if your input to Colorful-Walk has a “yes” answer.
Since Set-Cover is a well-known NP-hard problem, it would then follow that Colorful- Walk is NP-hard.
(Hint: for your construction of the directed graph G, try something like the picture below, with appropriate colors assigned to edges. Remember that in the actual description of your construction, you are given X, S, and K; you are not given T , which may or may not exist, since the goal is to determine whether the answer is “yes” or “no”.)
Solution: We describe a polynomial-time reduction from Set-Cover to Colorful-Walk.
The Reduction. We are given an input to Set-Cover, i.e., a set X of N elements, a collection of M subsets S = {S1,…,SM} where each Si ⊆ X, and a number K. We want to construct an input to Colorful-Walk, i.e., a directed graph G, a vertex s, and a coloring c(·) of the edges, and a number l.
Here is our construction. Without loss of generality (by relabeling), say X = {1, . . . , N }.
We define k = N (i.e., the colors are X).
Foreachj∈{1,…,K+1},wecreateavertexsj inG.
For each j ∈ {1,…,K} and i ∈ {1,…,M}, we create a new path πi,j from sj to sj+1 in G. This path πi,j has length |Si| and the colors of the edges of πi,j are precisely the set Si. (The order in which the colors appear along the path would not matter.)
We define s = s1.
We define l = N.
(Note that the resulting graph G is a DAG, with source s = s1 and sink sK+1.) Clearly, this construction can be carried out in polynomial time.
Correctness. We need to prove the following statement: there exists a subcollection T ⊆ S of K subsets such that the union of the subsets in T includes all elements of X ⇐⇒ there exists a walk in G that starts at s and encounters at least l distinct colors.
Proof of (=⇒): Suppose we have a subcollection T = {Si1 , . . . , SiK } of K subsets such that the union of the subsets in T includes all elements of X. We define a walk from s = s1, where for each j ∈ {1,…,K}, we go from sj to sj+1 via the path πij,j. The colors along this walk is precisely Si1 ∪···∪SiK , which is all of X. So, the walk encounters all l = N colors.
Proof of (⇐=): Suppose we have a walk τ in G that starts at s = s1 and encounters at least l distinct colors. We define a subcollection T as follows. For each j ∈ {1, . . . , K} and i ∈ {1,…,M}, if the walk τ uses (all or some) edges from the path πi,j, we add the subset Si to the collection T . Note that for each j, the walk τ can only visit at most one path from {π1,j,…,πM,j}, so at most one subset Si is added to T per j. Thus, the total number of subsets in T is at most K. We can make the number exactly K by adding extra subsets. Since the walk uses at least l distinct colors, the union of the subsets in T must contain at least l distinct colors. Since l = N, this means that the union of the subsets in T is all of X.
We conclude that Colorful-Walk is NP-hard.
Problem 11.2: By now, everyone has heard of Wordle, the online word-guessing game. Here, you will consider a tougher variant of the game, where the word length n is a variable, all strings of length n from a fixed alphabet are legal words (no dictionary needed!), and after each
guess, you are only told whether there is a green (matching) position, but not the number of green (nor yellow) positions, nor where they are exactly. You will show that in this version of the game, just deciding whether there exists a solution after a series of guesses is already hard (so forget about the question of how to generate a good next guess!).
If you didn’t follow the above paragraph, don’t worry—here is the precise definition of our problem: For two strings y and z of length n, first define match(y,z) to be true if there exists a position k such that the k-th symbol of y is equal to the k-th symbol of z, and false otherwise. The statement of the Tough-Wordle problem is as follows:
Input: a finite alphabet Σ, a list of m strings y1,…,ym ∈ Σn, and m Boolean values b1, . . . , bm ∈ {true, false}.
Output: “yes” iff there exists a string z ∈ Σn such that match(yi,z) = bi for each i = 1,…,m.
(Example: on the input with Σ = {A, B, C}, y1 = AAAA, b1 = true, y2 = BBCC, b2 = true, y3 = BCAB, b3 = false, the answer is “yes”, e.g., by choosing z = ABCC.)
Describe a polynomial-time reduction from 3SAT to Tough-Wordle. Follow these steps:
Given an input to 3SAT (i.e., a Boolean formula F in 3CNF form), describe a con- struction of an input to Tough-Wordle (i.e., an alphabet Σ, and a list of strings and Boolean values). Check that your construction takes polynomial time.
Prove that F is satisfiable if and only if your input to Tough-Wordle has a “yes” answer.
Since 3SAT is NP-hard, it would then follow that Tough-Wordle is NP-hard.
(Hint: in your construction, an alphabet of size 3 (0, 1, and an extra symbol) would be sufficient. Suppose F has n variables and m clauses. Intuitively, the string z (if exists) should correspond to a satisfying assignment of F (if exists). For each clause Ci, construct a string yi of length n (and a corresponding Boolean value bi) to somehow make sure that z contains at least one true literal of Ci. Also, construct an extra string to somehow make sure that z uses only 0s and 1s and not the extra symbol… Remember that in the actual description of your construction, all you are given is F ; you are not given a satisfying assignment, which may or may not exist, since the goal is to determine whether the answer is “yes” or “no”.)
Solution: We describe a polynomial-time reduction from 3SAT to Tough-Wordle.
The Reduction. We are given an input to 3SAT, i.e., a Boolean formula F in 3CNF form, say, with n variables x1,…,xn and m clauses C1,…,Cm. We want to construct an input to Tough-Wordle, i.e., an alphabet Σ, a list of strings y1,…,ym′, and a list of Boolean values b1,…,bm′.
Here is our construction. We choose Σ = {0, 1, 2}. For each clause Ci (i ∈ {1, . . . , m}), we define a string yi = yi1yi2 · · · yin of length n, with
1 if xj is a literal in the clause Ci yij = 0 ifxj isaliteralintheclauseCi
2 otherwise. 3
(As the clause Ci has length three, the string yi consists mostly of 2’s, except in three places.) We set the corresponding Boolean value bi = true.
To finish the construction, we define one additional string ym+1 = 22 · · · 2 consisting of n 2’s and let bm+1 = false. (The total number of strings is thus m′ = m + 1.)
Clearly, this construction can be carried out in polynomial time.
Correctness. We need to prove the following statement: F is satisfiable ⇐⇒ there exists a
stringz∈{0,1,2}n suchthatmatch(yi,z)=bi foreachi=1,…,m+1.
Proof of (=⇒): Suppose F is satisfied by some truth assignment A of the variables x1, . . . , xn. Define a string z = z1 ···zn of length n, where zj is set to 1 if xj is assigned to true in A, and 0 otherwise.
We claim that match(yi,z) = bi for every i ∈ {1,…,m + 1}. To see this, take a clause Ci (i ∈ {1, . . . , m}). Since Ci is satisfied by A, some literal in Ci must be assigned to true. If this literal is xj, then both zj = 1 and yij = 1; if this literal is xj, then both zj = 0 and yij = 0. In either case, match(yi,z) = true. To finish, observe that match(ym+1, z) = false, since z does not contain any 2’s.
Proof of (⇐=): Suppose z ∈ {0,1,2}n is a string such that match(yi,z) = bi for each i ∈ {1, . . . , m + 1}. In particular, match(ym+1, z) = false, implying that z consists of only 0’s and 1’s. Define an assignment A where xj is set to true if zj = 1, and false otherwise.
We claim that F is satisfied by A. To see this, take a clause Ci (i ∈ {1,…,m}). Since match(yi, z) = true, we must have yij = zj for some position j. If zj = 1, then xj is set totrueinAandappearsinCi;ifzj =0,thenxj issettotrueinAandappearsinCi. In either case, the clause Ci is satisfied by A.
We conclude that Tough-Wordle is NP-hard.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com