When an element of S has been examined mark it and find another element in S which has not yet been examined. If all the elements of S have been examined and 2 is not in S, then there is not a path from 1 to 2. Since reachability is in P , by the reduction argument given above, 2-SAT in P . Assign all vertices reachable from v the value true and assign their negations the value false . Repeat steps 1 and 2 until all vertices have been visited or have been assigned a truth value.
All undetermined variables can either be true or false and their negation is the opposite.