CS代写 CSCI 570 Exam 3 - PowCoder代写

Review Session CSCI 570 Exam 3

Quick Concept Review: Any Doubts?
● Decision Problems?

● P: Decision problems deterministically solvable in polynomial time
● NP: Decision problems deterministically verifiable in polynomial time (Certificate? Verifier?)
● Polynomial-time Reducible?
● NP-Hard: A problem H is NP-Hard if every problem in NP can be reduced to H in polynomial time.
● NP-Complete? (How to prove that a given decision problem is NP-Complete?)
● Why are reductions useful and how to use them?
● Example: To show that IND-SET is NP-Hard, why is it sufficient to show that 3-SAT (already known to be NP-Complete) can be reduced to IND-SET?

NP- True / False Questions
If INDEPENDENT SET can be reduced to a decision problem X, then X can be reduced to INDEPENDENT SET.

If INDEPENDENT SET can be reduced to a problem X, then X can be reduced to INDEPENDENT SET.
False. If X is in NP, then it would be guaranteed true, but cannot claim without that
information.

NP- True / False Questions
All the NP-hard problems are also in NP.

All the NP-hard problems are also in NP.
False. The NP-hard problems that are in NP are called NP-complete but that’s only a strict subset of
the NP-hard problems.

NP – Long Question 1
The CLIQUE Problem: Given an undirected graph G = (V, E), and a positive integer k, decide whether the graph G contains a clique of size at least k.
A clique is a subset of vertices in graph G such that every pair of vertices is connected by an edge. Prove that the CLIQUE problem is NP-complete.

The CLIQUE Problem: Given an undirected graph G = (V, E), and a positive integer k, decide whether the graph G contains a clique of size at least k.
A clique is a subset of vertices in graph G such that every pair of vertices is connected by an edge. Prove that the CLIQUE problem is NP-complete.
a) CLIQUE is in NP: A subset of vertices V’, claimed to be a part of the clique – can be a certificate.
– The number of vertices are at least k.
– There is an edge between any two vertices in V’.
– Runs in polynomial time?

The CLIQUE Problem: Given an undirected graph G = (V, E), and a positive integer k, decide whether the graph G contains a clique of size at least k.
b) IND-SET to CLIQUE
IND-SET Problem: Given (G,k), is there an independent set of size at least k?
Construction: Create an instance of the CLIQUE problem using (GC, k) – GC being the complement of G (edges reversed)
1) If G has an independent-set of size at least k, means that any two vertices in this set
do not have an edge in G -> means that they have an edge in GC -> i.e. the same set of vertices form a clique in GC -> proving that GC has a clique of size k.
2) If GC has a clique of size at least k, the same vertices would form an independent set in G.
3SAT to CLIQUE –
– Key Idea: Literals in the clause → Vertices in the graph. Connect vertices from different
clauses that can be consistently set to 1 with each other.
– See Theorem 34.11 in Coreman

NP – Long Question 2
Suppose you move to a new city. The city is defined by a directed graph G=(V,E) and each edge e ∈ E has a non-negative cost ce associated to it. Your living place is represented as a node s ∈ V. There is a set of landmarks X (a subset of V), which you want to visit. To plan your roaming around efficiently, you are interested in finding a subgraph G’=(V’,E’) that contains a path from s to each x ∈ X while minimizing the total edge cost of E’. The decision problem (call it ROAM) is, given a graph G=(V,E) with non-negative costs, vertex subset X of V, a node s ∈ V, and a number k, does there exist a subgraph G’=(V’,E’) that contains a path from s to each x ∈ X, having a total edge cost of E’ at most k? Show that ROAM is NP-complete with a reduction from SAT.

Let’s take the below example with X = {2, 4} and s = r. Is there a way to select edges such that all nodes in X are reachable by s and the total edge cost is at most 9?

The solution to above problem can be seen below. We can see that both nodes 2 and 4 are reachable by r and total edge cost is 5 + 2 + 2 = 9.

Suppose you move to a new city. The city is defined by a directed graph G=(V,E) and each edge e ∈ E has a non-negative cost ce associated to it. Your living place is represented as a node s ∈ V. There is a set of landmarks X (a subset of V), which you want to visit. To plan your roaming around efficiently, you are interested in finding a subgraph G’=(V’,E’) that contains a path from s to each x ∈ X while minimizing the total edge cost of E’. The decision problem (call it ROAM) is, given a graph G=(V,E) with non-negative costs, vertex subset X of V, a node s ∈ V, and a number k, does there exist a subgraph G’=(V’,E’) that contains a path from s to each x ∈ X, having a total edge cost of E’ at most k? Show that ROAM is NP-complete with a reduction from 3SAT.
a) Show that ROAM is in NP
Solution: We show that a subgraph G’ as a certificate. Certifier checks that all the nodes in X are
reachable – can be done using DFS, thus in poly-time. Then check the total edge weight is within k –
doable in linear (hence poly-) time.

Suppose you move to a new city. The city is defined by a directed graph G=(V,E) and each edge e ∈ E has a non-negative cost ce associated to it. Your living place is represented as a node s ∈ V. There is a set of landmarks X (a subset of V), which you want to visit. To plan your roaming around efficiently, you are interested in finding a subgraph G’=(V’,E’) that contains a path from s to each x ∈ X while minimizing the total edge cost of E’. The decision problem (call it ROAM) is, given a graph G=(V,E) with non-negative costs, vertex subset X of V, a node s ∈ V, and a number k, does there exist a subgraph G’=(V’,E’) that contains a path from s to each x ∈ X, having a total edge cost of E’ at most k? Show that ROAM is NP-complete with a reduction from 3SAT.
Hints for construction
‘Satisfy ALL clauses’ VS ‘Reach ALL nodes in X’
Variables serve as ways to satisfy clauses VS nodes/edges in G serve as ways to satisfy the
reachability constraints of X,

(b) Reduction from SAT: Construct
A new node r for living place.
Nodes xi and ~xi for each literal, all connected to r. Nodes ci for each clause, connected to its literals. Nodes ui for each variable, connected to xi & ~xi All edges have weight 1.
Subset X contains all ui and ci
K = 2n + m (as used in the claim next) (n = #vars, m = #clauses)

(b) Construction:
A new node r for living place.
Nodes xi and ~xi for each variable, all connected to r.
Nodes ci for each clause, connected to corresponding literals.
Nodes ui for each variable connected to xi and ~xi All edges have weight 1.
Subset X contains all ui and ci
(c) Claim: Given 3-SAT instance (i.e. the 3CNF formula) has a solution (i.e. a satisfying assignment) if and only if the constructed graph has a subgraph G’ containing paths from r to each x in X, with total edge weight at most 2n + m

(d) SAT has a satisfying assignment => Constructed graph has a subgraph with routes from r to each x in X with weight at most 2n + m
Proof: Consider the satisfying assignment. For any xi, let Li be the literal that is true (i.e. xi or ~xi). Construct the subgraph by including
1) The nodes corresponding to each Li (alongwith the source node r & all the destination nodes ui and cj)
2) All the edges r -> Li and Li -> ui so that ui is reachable from r (thus, 2n such edges). Further, since the subgraph is constructed from a satisfying assignment, some literal in each clause is true and we add the edge from the corresponding literal node to the clause node (thus, m such edges) so that all cj are reachable.

(e) Constructed graph has a subgraph spanning X with weight at most 2n + m => SAT has a satisfying assignment
Proof: Consider the spanning subgraph H.
1) H must have the node Li and edges r -> Li and Li -> ui for either Li = xi or Li = ~xi so that ui is reachable from r (thus, 2n such edges, and n nodes).
2) Further, for each clause, there must be an edge in H from the literal node to the clause node (thus, m such edges) so that it’s reachable from r. Additionally if this literal is not already included from 1), there must be an edge from r to this literal to make the clause node reachable.
Since H has a total edge weight at most 2n + m, it must have precisely the n nodes and 2n+m edges mentioned above. Then, we obtain an assignment by setting each xi to true/false so as to make the corresponding Li (that is included in H) true. This is a complete assignment since H includes a node for each variable as shown in 1). Further this is a satisfying assignment since for each clause, one of the literals (which makes it reachable from r in H) becomes true, thus satisfying the clause.

NP – Long Question 3
Given an undirected connected graph G = (V, E) in which a certain number of tokens t(v)≥1 placed on each vertex v. You will now play the following game. You pick a vertex u that contains at least two tokens, remove two tokens from u and add one token to any one of adjacent vertices. The objective of
the game is to perform a sequence of moves such that you are left with exactly one token in the whole graph. You are not allowed to pick a vertex with 0 or 1 token. Prove that the problem of finding such a sequence of moves is NP-complete.

Given an undirected connected graph G = (V, E) in which a certain number of tokens t(v)≥1 placed on each vertex v. You will now play the following game. You pick a vertex u that contains at least two tokens, remove
two tokens from u and add one token to any one of adjacent vertices. The objective of the game is to perform a sequence of moves such that you are left with exactly one token in the whole graph. You are not allowed to pick a vertex with 0 or 1 token. Prove that the problem of finding such a sequence of moves is NP-complete.
Forward Claim:
If there is a Hamiltonian path in the graph, then there will be a valid sequence of moves for at least one call to the above problem. Let’s say the hamiltonian path in G is the sequence of nodes x1, x2, ….. xn. Then, when we use the above problem considering x1 as a starting point, we can go through the list of nodes in the hamiltonian path. We know that x1 has two tokens and rest of the nodes have 1 token. When we consider x1 as a starting point, we delete its two tokens and add a token to x2, so now x2 has two tokens. Once a node gets visited, there will be 0 tokens in that node and will have added a token to the next node in the sequence of moves(making its tokens 2). Since the path visits every node, we have removed the one token on each of the node. When we visit last vertex, we remove its tokens and add one token to a random neighbour node and hence, only one token is remaining in the entire graph.

Given an undirected connected graph G = (V, E) in which a certain number of tokens t(v)≥1 placed on each vertex v. You will now play the following game. You pick a vertex u that contains at least two tokens, remove two tokens
from u and add one token to any one of adjacent vertices. The objective of the game is to perform a sequence of moves such that you are left with exactly one token in the whole graph. You are not allowed to pick a vertex with 0 or 1 token. Prove that the problem of finding such a sequence of moves is NP-complete.
Backward Claim:
If there is a valid sequence of move for any of the V calls to the above problem, then there is a Hamiltonian path in G. Let’s say there is a valid sequence of moves x1, x2, …. xn, xn + 1, when we consider the problem with only x1 having two tokens. We can see that the only possible starting point is x1 as there is no other node with two tokens. Also, when we push a token to node x2, our next move needs to be removing two tokens from x2, as there is no other node with two tokens. Once we have visited a node, we can’t visit it again as the node now has 0 tokens and pushing a token to it makes the number of tokens 1. Hence, x1, x2, …. xn are unique nodes. We also need to visit each node at least once so that there is no more than 1 token remaining in the entire graph. This shows that the path x1, x2, ….. xn has visited each node exactly once. Since we can push token only to a neighbour node, the sequence x1, x2, ….., xn will be a valid path and hence, will be a valid hamiltonian path.

Linear Programming
Review Session CSCI 570 Exam 3

Minimum Weighted Set Cover
Given a set U of n elements, and m subsets of U denoted by Sj, j ∈ 1, 2, …, m, and a weight wj for each subset, find a k-approximation of the minimum-weighted set cover.
You are given that the union of all Sj’s equals U and each element in U belongs to at most k subsets. Weight of a set cover is the sum of weights of the subsets included in the set cover.
Use Integer Linear Programming to solve this problem.

Steps of the solution
1. Formulate the problem as an Integer Linear Programming (ILP) problem
2. Relax the constraints to convert to a Linear Programming (LP) problem
3. Use rounding to get an approximate solution
4. Show that the approximate solution is a valid set cover
5. Prove that the approximate solution is at most k times the optimal solution

Step 1: Formulate as ILP
Suppose U = {u1, u2, … , un}
Define a decision variable xi for each subset Si, i = 1 to m xi = 1 if Si is included in the set cover, else 0
For a collection of subsets to be a set cover, each element should be present in its union.

Step 1: Formulate as ILP

Step 2: Relax to LP
Drop the requirement that xi ∈ {0, 1}, and convert it to 0 ≤ xi ≤ 1
Now the constraints are linear and we have converted the integer linear programming problem to a linear programming problem which can be solved in polynomial time
Let {x*} be the LP solution, and WLP = ∑ wi xi*

Step 3: Rounding to get approximate solution
We include a set Si in the set cover if xi* ≥ 1/k
So our approximate set cover is F = {Si | xi* ≥ 1/k}

Step 4: Show that your approximate solution is valid
We show that F is indeed a correct set cover. Consider above constraint for each element ui.
Each ui belongs to at most k subsets. Therefore it is not possible for all xj < 1/k because then ∑ xj < ∑ 1/k < k ✕ 1/k = 1, violating above constraint. Therefore at least one of xj should be ≥ 1/k Therefore at least one of Sj will be included in our approximate set cover F Therefore all elements are covered by F Step 5: Prove that your approximate solution ≤ k optimal solution Let FOPT be the minimum-weighted set cover, and WOPT = sum of weights of subsets included in FOPT WOPT is the value of the objective function of the original ILP problem WLP is the value of the objective function of the relaxed LP problem Therefore WLP ≤ WOPT Step 5: Prove that your approximate solution ≤ k optimal solution Let Wapprox = sum of weights of subsets included in our approximate set cover F Therefore Wapprox ≤ k WLP Combining with WLP ≤ WOPT , we get Wapprox ≤ k WOPT Manufacturing Problem A company manufactures four items A, B, C, and D on two machines X and Y. The time (in minutes) to manufacture one unit of each item on the two machines is shown on the right. The profit per unit for A, B, C, and D is $10, $12, $17, and $8 respectively. The floor space taken up by each unit of A, B, C, and D is 0.1, 0.15, 0.5, and 0.05 sq. meters respectively. Total floor space available is 50 sq. meters. Customers require that twice as many units of B should be produced as C. Machine X is out of action (maintenance/breakdown) for 5% of the time, and machine Y for 7% of the time. Assuming a working week 35 hours long, formulate the problem of how to manufacture these products so as to maximize profit as a linear program. You don’t need to solve it. Time taken 1. Let xA, xB, xC, and xD be the units of A, B, C, D manufactured by machine X. Let yA, yB, yC, and yD be the units of A, B, C, D manufactured by machine Y. 2. Objective Function: Maximize 10(xA + yA) + 12(xB + yB) + 17(xC + yC) + 8(xD + yD) 3. Constraints: a. Floor Space 0.1(xA + yA) + 0.15(xB + yB) + 0.5(xC + yC) + 0.05(xD + yD) ≤ 50 b. Customer requirement 2(xB + yB) = xC + yC 3. Constraints: c. Time constraint 10 xA + 12 xB + 13 xC + 8 xD ≤ 0.95 x 35 x 60 29 yA + 19 yB + 33 yC + 23 yD ≤ 0.93 x 35 x 60 d. Non-negative units xA, xB, xC, xD, yA, yB, yC, yD ≥ 0 Spaceship Radar A set of n space stations need your help in building a radar system to track spaceships traveling between them. The ith space station is located in 程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts