A Survey on the Fine-grained Complexity of Constraint Satisfaction Problems Based on Partial Polymorphisms
Miguel Couceiro, Lucien Haddad and Victor Lagerkvist
Constraint satisfaction problems (CSPs) are combinatorial problems with strong ties to universal algebra and clone theory. The recently proved CSP dichotomy theorem states that each finite-domain CSP is either solvable in polynomial time, or that it is NP-complete. However, among the intractable CSPs there is a seemingly large variance in how fast they can be solved by exponential-time algorithms, which cannot be explained by the classical algebraic approach based on polymorphisms. In this contribution we will survey an alternative approach based on partial polymorphisms, which is useful for studying the fine-grained complexity of NP-complete CSPs. Moreover, we will state and discuss some challenging open problems in this research field.
Keywords: Constraint satisfaction problems, universal algebra, clone theory, computational complexity