Graph orientations with no sink and an approximation for a hard case of #SAT

Abstract

Graph orientation problems have a long pedigree both in pure mathematics and theoretical computer science. We consider here all of the major combinatorial problems associated with sink-free graph orientations: decision, construction, listing, counting, approximate counting and approximate sampling. We also observe a close connection between sink-free graph orientations and a restricted form of the SAT problem in which each variable may appear at most twice; we name this Twice-SAT. We show that this problem is No. P-complete, and offer a fully polynomial randomized approximation scheme for it.