GR2 Flashcards
1
Q
If x and ¬x are in same SCC, then we know…
A
that the formula is is NOT satisfiable
2
Q
If x and ¬x are not in same SCC, then we know…
A
that the formula IS satisfiable
3
Q
If S is a sink SCC, then we know that….
A
S’ is a sink SCC
4
Q
(a ∨ b)
A
¬a –> b, ¬b –> a
5
Q
If x and ¬x are part of the same strongly connected component, then…
A
we know that the formula is NOT satisfiable
6
Q
If x and ¬x are NOT part of the same strongly connected component, then…
A
we know that the formula IS satisfiable
7
Q
runtime of 2SAT
A
O(n + m)
8
Q
2SAT algorithm explained
A
- Find sink SCC, S
- Set S = T (satisfy all literals in S)
- Rip S out from graph
- S’ will then be the source SCC (so setting S’ = F has no effect). So rip this out too.
- Repeat
