Graph Theory37 sections · 1633 units
Open in Course

Constructing the Assignment

(SCC topological order)

Assign each SCC a topological index. The exact numbering depends on your SCC algorithm, but higher index typically means earlier in topological order. For each topping i, compare SCC(x_i) and SCC(NOT x_i). If SCC(x_i) > SCC(NOT x_i), include topping i on the pizza (output +).

Otherwise exclude it (output -). This assignment is guaranteed to satisfy all customer preferences. It is a valid solution to the 22-SAT instance.