GR2

Question 1

If x and ¬x are in same SCC, then we know…

Answer 1

that the formula is is NOT satisfiable

Question 2

If x and ¬x are not in same SCC, then we know…

Answer 2

that the formula IS satisfiable

Question 3

If S is a sink SCC, then we know that….

Answer 3

S’ is a sink SCC

Question 4

(a ∨ b)

Answer 4

¬a –> b, ¬b –> a

Question 5

If x and ¬x are part of the same strongly connected component, then…

Answer 5

we know that the formula is NOT satisfiable

Question 6

If x and ¬x are NOT part of the same strongly connected component, then…

Answer 6

we know that the formula IS satisfiable

Question 7

runtime of 2SAT

Answer 7

O(n + m)

Question 8

2SAT algorithm explained

Answer 8

1. Find sink SCC, S
2. Set S = T (satisfy all literals in S)
3. Rip S out from graph
4. S’ will then be the source SCC (so setting S’ = F has no effect). So rip this out too.
5. Repeat