Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem

The inverse satisfiability problem over a set of relations Gamma (INv-SAT(Gamma)) is the problem of deciding whether a relation R can be defined as the set of models of a SAT(Gamma) instance. Kavvadias and Sideri (1998) [15] obtained a dichotomy between P and co-NP-complete for finite r containing the two constant Boolean relations. However, for arbitrary constraint languages the complexity has been wide open, and in this article we finally prove a complete dichotomy theorem for finite languages. Kavvadias and Sideris techniques are not applicable and we have to turn to the more recent algebraic approach based on partial polymorphisms. We also study the complexity of the inverse constraint satisfaction problem prove a general hardness result, which in particular resolves the complexity of INvERSE k-COLOURING, mentioned as an open problem in Chen (2008) [8]. (C) 2020 Elsevier Inc. All rights reserved.Funding Agencies|German Research Foundation (DFG)German Research Foundation (DFG) [622397]; Swedish Research Council (VR)Swedish Research Council [2019-03690]; National Graduate School in Computer Science(CUGS), Sweden