Graph Theory37 sections · 1633 units
Open in Course

Finding an Assignment

(Using SCC order)

If the formula is satisfiable, you need to construct an actual assignment. SCCs give you the order to make choices. Compute SCCs and their topological order in the condensation graph. For each variable, compare the SCC index of x and NOT x.

If SCC(x) comes after SCC(NOT x) in topological order, set x to true. Otherwise set x to false. This construction always produces a valid assignment when one exists.