Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP 360 Fall 2023

Assignment 5

Due: Thursday, November 30th, 2023 at 8:00pm

Please submit the assignment on Crowdmark by the due date. In all problems below where you are asked to give an efficient algorithm, you must also prove that your algorithm is correct and analyze its running time. If you use any sources other than the course textbook or the lecture notes (e.g. other textbooks, online notes, friends) please cite them for your own safety. Do not upload this assignment to any online repository. Also, a reminder that direct copying from sources is not permitted, and solutions must be in your own words.

Questions

1. Consider the following variation of the Hamiltonian Path problem, in which a limited number of vertices can be reused. The input is a directed graph G = (V, E) with two distinguished vertices s = t ∈ V , and a positive integer k ≥ 1. The output is to decide if there is a path from s to t in G, such that every vertex is visited at least once and at most k vertices are visited more than once. Note that if a vertex v is revisited, then v can be revisited an unlimited number of times. However, we can only revisit up to k vertices in this manner. [12]

(a) Give an example of a directed graph G = (V, E) with distinguished vertices s = t such that G has no Hamiltonian path from s to t, but G has a Hamiltonian path if we are allowed to revisit one vertex.

(b) Prove that this problem is NP-Complete.

2. In chess, a king threatens each of the squares that are immediately adjacent to it. For in-stance, consider a standard 8 × 8 chessboard, where the rows and columns are indexed by 1, 2, . . . , 8. If a king is sitting on the square (4, 5), then it threatens the 8 squares surrounding it: (3, 4),(3, 5),(3, 6),(4, 4),(4, 6),(5, 4),(5, 5), and (5, 6). [5]

Consider the following optimization problem. Recall [n] = {1, 2, . . . , n} for any positive integer n. The input is a positive integer n ≥ 1, and a set S ⊆ [n] × [n] of squares that contain kings on an n × n chessboard. The output is the largest subset R ⊆ S such that no two kings on squares in R threaten each other.

Give a polynomial-time 8-approximation algorithm solving this problem.

3. Consider the MAX-SAT problem. As input, you are given a CNF formula F. The output is to find an assignment to F that satisfies as many clauses as possible. [5]

Prove that the following is a 2-approximation to the Max-SAT problem. Either output the all-1s or all-0s assignment, whichever satisfies more clauses.

4. A common problem that comes up in the design of computer networks is monitoring. Consider the following. You have a network of servers N , containing a set of servers S. Each server s ∈ S is connected, via a direct two-way link, to up to 4 other servers in the network. Some of these servers are deployment servers, meaning that they are workhorses, doing standard computational work. Other servers are monitors, meaning that they monitor and coordinate the work of local servers in the network. Every deployment server needs to be monitored by some monitoring server. However, monitoring servers can only monitor the (up to 4) servers that they are directly connected to. Also, some servers have older hardware, and are therefore more expensive to set up as monitoring servers when compared to leaving them as deployment servers. The goal, then, is to choose a subset of servers to become monitoring servers such that [10]

• Every deployment server is monitored by some monitoring server.

• The total cost to set up the monitoring servers is minimized.

We can formalize this as an optimization problem. The input is a network N , which contains a set of servers S, for each server s ∈ S the list of ≤ 4 servers that s is directly connected to, and the cost c(s) ≥ 0 it takes to turn server s into a monitoring server. The goal is to find a set of servers U ⊆ S such that (a) every server t 6∈ U is adjacent to some server in U, and (b) P u∈U c(u) is minimized.

Give a polynomial-time, 5-approximation algorithm solving this problem.

5. The 2-factor approximation algorithm we saw for the Minimum Vertex Cover problem means that [10] there is a polynomial-time algorithm that will output a vertex cover that is no more than twice the size of the minimum vertex cover. Another natural notion of approximation uses an additive factor. Given a number c, an algorithm is an additive c-approximation for Minimum Vertex Cover if on any input graph G, the algorithm outputs a vertex cover of size at most α + c, where α is the size of the smallest vertex cover of G.

Show that if there is a polynomial-time, additive 2-approximation algorithm for the Minimum Vertex Cover problem, then P = NP.