Advanced Algorithms · End Term · 24 Dec 2023 · September 2023 term · Set ADI4

Question 17: In the MIN-2-SAT problem, we are given a 2-CNF formula \…

Question 17

+3 marksOne correct option

In the MIN-2-SAT problem, we are given a 2-CNF formula $\phi$ and an integer $k$ , and the objective is to decide whether there exists an assignment for $\phi$ that satisfies at most $k$ clauses.

Consider the following branching algorithm for the problem.

If there is a variable $x$ that occurs only positively in $\phi$ , observe that there exists an optimal assignment that sets it to $0$ . Similarly, if there is a variable $x$ that occurs only positively in $\phi$ , there exists an optimal assignment that sets it to $1$ . Once we perform this preprocessing, assuming that have clauses remaining, we have the following guarantee:

Every variable has at least one positive and one negated occurrence.

Now we can branch exhaustively on the settings of variables. The overall algorithm is summarized in the following pseudocode:

text

1MINSAT(phi,k):
2    if there is a variable x that occurs only as a positive literal:
3        set x to 0
4    if there is a variable x that occurs only as a negated literal:
5        set x to 1
6
7    if phi is empty:
8        return YES
9    if phi is not empty and k <= 0:
10        return NO
11
12    Let x be any variable that occurs in phi.
13    return MINSAT(phi|[x = TRUE],k-1) OR MINSAT(phi|[x = FALSE],k-1)

Which of the following statements is true?

A
In both branches of the algorithm, at least one clause is falsified.
B
In both branches of the algorithm, at least one clause is satisfied.
C
In both branches of the algorithm, at least two clauses are falsified.
D
In both branches of the algorithm, at least two clauses are satisfied.

Show answer

Correct answer

B
In both branches of the algorithm, at least one clause is satisfied.

See the whole paper Take it as a mock test

Question 17 of 24 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) End Term paper sat on 24 Dec 2023, in the September 2023 term (IIT M DEGREE FN EXAM FDB1 24 Dec 2023). It carries 3 marks.

Question 17: In the MIN-2-SAT problem, we are given a 2-CNF formula \…

Question 17

More questions from this paper