Reference no: EM133026418

Question 1. Find the errors in the proofs of the following two wrong claims.

(a) Wrong claim: The following problem is NP-complete.

- Input: A CNF Φ.
- Question: Does Φ have exactly one truth assignment that satisfies it?

(b) Wrong claim: The following problem is NP-complete.
- Input: A 4-regular (i.e. all the vertices have degree 4) graph G.
- Question: Is there a subset S ⊆ V(G) that is both an independent set and a vertex cover.

Question 2. Consider a generalization of linear programming, where in addition to the original type of constraints, we can also include absolute-value constraints that are of the form:

|a₁x₁ + ....... + a_nx_n| = c,

where a₁'s and c are integers, and x₁,... , x_n are variables. Prove that the following problem is NP-complete.
- Input: A (minimization) generalized linear program as described above, and a number k E Z.
- Question: Is the optimal answer ≤ k?

Question 3. Prove that the following problem is NP-complete:

- Input: An n x m matrix A with integer entries, and an integer k ≥ 0.
- Question: Is it possible to negate¹ at most k rows of A such that in the resulting matrix, every column contains at least one strictly positive integer?

Question 4. Consider an undirected graph representing a social network. Suppose that some people are infected in this network, and the infection spreads by the following rule: If a node is infected, then at the next round, all its neighbours will also become infected. Prove that the following problem is NP-complete.

- Input: A graph G (with no infected nodes), two integers r,k ≥ 0.
- Question: Is it possible to initially infected at most k nodes in G such that after r rounds, all the nodes will become infected?

Question 5. Prove that the following problem is NP-complete.

- Input: a set of integers a₁, ...... a_k and a target integer M.
- Question: Are there signs e₁, .... , e_n ∈ {-1, 1} such that e₁a₁ + .... + e_na_n = M?

Question 6. Either prove that the following problem is NP-complete or explain how it can be solved in polynomial time: We are given a list of n tasks, and we want to select a subset of these tasks to perform. For every 1 ≤  i ≤ n, the i-th task has cost c_i > 0, revenue k > 0, a list of prerequisite tasks S_i ⊆ {1, , n}, and a list of incompatible tasks U_i ⊆ {1, , n}. This means that if we decide to select the task i, we also have to select every task in S_i, and moreover we will not be allowed to select any task from U_i.

• INPUT: The number of tasks it n ∈ N, the costs c_i, revenues b_i, and sets S_i and U_i for all i ∈ {1, ..... ,n}. A number k.

• QUESTION: Is it possible to choose a subset of tasks that satisfies the prerequisite and incompatibility requirements and moreover earns us at least k. That is, the total revenue minus the total cost of the selected tasks is at least k?