Classification of homomorphisms to oriented cycles and of k-partite satisfiability

We show that, for every choice of an oriented cycle H, the problem of wheth er an input digraph G has a homomorphism to H is either polynomially solvab le or NP-complete. Along the way, we obtain simpler proofs for two known po lynomial cases, namely, oriented paths and unbalanced oriented cycles, and exhibit two new simple polynomial cases of balanced oriented cycles. The mo re difficult cases of the classification are handled by means of a new prob lem, the bipartite boolean satis ability problem. In general, the k-partite boolean satis ability problems are shown to be either polynomially solvabl e or NP-complete, thus generalizing Schaefer's classification of boolean sa tis ability problems.