Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Assignment 4 CSE 565
INSTRUCTIONS:
1. Use the provided latex template to write your solutions.
2. Submit your solution to Gradescope: make sure only one of your group members submits. After
submitting, make sure to add your group members.
3. Problems 4–6 are optional. You don’t need to submit them and they won’t be graded.
Problem 1 (10 points).
Show that the geography problem introduced in class is in PSPACE.
Problem 2 (10 points).
You are given a set P = {p1, ..., pn} of n points in the plane given by their integer coordinates, a set Q =
{q1, ...,qm} of m curves given by m well defined equations. Suppose you can determine whether a point pi
lies on curve qi or not in O(1) time. A curve cover X of P is a subset of Q which satisfies that every point of
P lies on at least one curve of X.
(1) Your task is to find a curve cover X0 with minimized size. Can you (always) complete this task in
polynomial time? If yes, design a polynomial-time algorithm to complete this task. Otherwise, explain why
(e.g. prove it is NPC and claim there is no polynomial-time solver for NPC problems yet).
(2) You are informed that there is one curve cover of P with size of positive integer k (0 < k n ). You
only know its size k, but don’t know what curves are in the curve cover. Can you find size-minimized curve
cover X0 in polynomial time with respect to n? Please note that size of X0 could possibly be k or smaller.
If yes, design a polynomial-time algorithm to complete this task. Otherwise, explain why (e.g. prove it is
NPC). You may consider k is a small positive integer constant.
Problem 3 (10 points).
You are given an undirected graph G = (V,E) and an integer k. We call a subset vertices V1 ⊂ V closed, if
for any two vertices u,v ∈ V1, there is no edge (u,v) in E, and there also does exist another vertex w ∈ V
such that both (u,w) ∈ E and (w,v) ∈ E. The Closed Sub-Set Problem is to decide whether G has a closed
subset of size at least k. Prove that the Closed Sub-Set Problem is NP-complete.
Problem 4 (0 points).
Prove that the 2SAT problem is in P.
Problem 5 (0 points).
Prove that the geography problem is in P if the underlying graph is acyclic.
Problem 6 (0 points).
A linear inequality over variables x1, · · · ,xk is an inequality of the form c1x1+ · · ·+ckxk ≤ b, where c1, · · · ,ck
and b are integers. Given a set of such inequalities, the problem is to decide whether it has an integeral
solution, i.e., whether one can assign integeral values to all variables in such a way that all inequalities are
satisfied. Prove that this problem is NP-complete.