Graph Theory37 sections · 1633 units
Open in Course

Quiz: Assignment Construction

Knowledge check

Check Your Understanding

After running SCC on a satisfiable 22-SAT instance, you pick the value for each variable based on topological order of SCCs. ¬x5\neg x_5 is in an SCC with higher topological number than x5x_5. What value does x5x_5 get?

  1. A.True, because x5x_5 appears first in topological order
  2. B.True, because you always pick the positive literal
  3. C.False, because you set the literal in the later SCC to true, which is ¬x5\neg x_5
  4. D.It depends on the other variables in the SCC
Start the roadmap to answer the quizzes and solve the challenges