Boolean Satisfiability with Transitivity Constraints

Randal E. Bryant, Miroslav N. Velev

We consider a variant of the Boolean satisfiability problem where a subset E of the propositional variables appearing in formula Fsat encode a symmetric, transitive, binary relatio…