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

COMP 360 Winter 2022

Assignment 3

Due: Friday, March 25th, 11:59pm

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 a CNF formula F = C1 ∧ C2 ∧ · · · ∧ Cm where every boolean literal occurring in F is negative. So, for example, F = (1∨2)∧(3∨4∨1) is such a formula, but F = x1∧(2∨4) is not. It is easy to see that such a formula F is always satisfiable, since setting xi = 0 for every i will satisfy all the clauses. However, we will show that it is hard to find satisfying assignments where we only set a bounded number of input variables to 0.

Formally, consider the following problem. As input, you receive a CNF formula F where every boolean literal in F is negative and a positive integer k. The goal is to decide if there is a satisfying assignment x to the variables of F such that at most k input variables are assigned to 0. Prove that this problem is NP-Complete.                   [10]

2. In this question, we consider modifications of the 3-Colouring problem where we bound the number of vertices that can receive a particular colour.        [15]

(a) First, consider the following version. As input, you receive a graph G = (V, E) with |V | ≥ 10. The goal is to decide if G admits a 3-colouring χ : V → {1, 2, 3} such that the colour 1 is used only 10 times (that is, χ labels the colour 1 on only 10 vertices). Give a polynomial-time algorithm for this version of 3-Colouring, and prove that your algorithm is correct.

(b) Consider the following modification of the 3-Colouring problem. As input, you receive a graph G = (V, E) such that the number of vertices n = |V | is divisible by 3. The goal is to decide if G admits a 3-colouring χ : V → {1, 2, 3} such that the number of vertices labelled by each colour is exactly n/3 (in other words, every colour is used an equal number of times). Prove that this problem is NP-Complete.

3. If x ∈ {0, 1}n is a boolean string, let ∈ {0, 1}n denote the new string obtained by flipping the bit in every coordinate in x. That is, i := 1 − xi for every i ∈ [n]. For a concrete example, if x = 101 then  = 010.

Consider the following variation of the SAT problem. As input, you receive a boolean formula F on variables x1, x2, . . . , xn (note that F is not necessarily a CNF formula). The goal is to decide if F has a satisfying assignment x ∈ {0, 1}n such that is also a satisfying assignment. Prove that this variant of SAT is NP-Complete.   [10]

4. Consider the following modification of the Subset Sum problem. As input you receive 2n + 1 positive integers w1, w2, . . . , wn, v1, v2, . . . , vn and W. The goal is to decide if there is a subset S ⊆ {1, 2, . . . , n} such that

Prove that this problem is NP-Complete.      [10]

5. Consider the following problem. As input, you receive a list of triples of integers                           [10]

L := {(x1, y1, z1),(x2, y2, z2), . . . ,(xn, yn, zn)} ⊆ Z3.

Each triple in the input represents the center of a 2 × 2 × 2 axis-aligned cube in R 3 . For instance, the triple (0, 0, 0) would represent the cube which is centered at the origin and has the points {+1, −1}3 as its 8 vertices. Given two triples (xi , yi , zi),(xj , yj , zj ) ∈ Z3 we say that the triples are intersecting if the two cubes represented by the triples have overlapping interiors. So, for instance, (0, 0, 0) and (0, 1, 0) would be intersecting triples since the interiors of the two corresponding cubes overlap. However, the points (0, 0, 0) and (0, 2, 0) would not be intersecting since the two cube interiors do not overlap; they only touch on their boundaries. The goal of this problem is the following: given the list of triples L, find the largest subset of triples O ⊆ L such that no pair of triples in O are intersecting.

Give an O(n2)-time 8-approximation algorithm for this problem and prove that your algorithm is correct.