2016/04/04 by Hubie Chen, Chen, Hubie, Benoît Larose +1
Computer Science · #Advanced Graph Theory Research #Artificial Intelligence (cs.AI) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1604.00932
openalex publication_date 2016/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The constraint satisfaction problem (CSP) involves deciding, given a set of variables and a set of constraints on the variables, whether or not there is an assignment to the variables satisfying all of the constraints. One formulation of the CSP is as the problem of deciding, given a pair (G,H) of relational structures, whether or not there is a homomorphism from the first structure to the second structure. The CSP is in general NP-hard; a common way to restrict this problem is to fix the second structure H, so that each structure H gives rise to a problem CSP(H). The problem family CSP(H) has been studied using an algebraic approach, which links the algorithmic and complexity properties of each problem CSP(H) to a set of operations, the so-called polymorphisms of H. Certain types of polymorphisms are known to imply the polynomial-time tractability of CSP(H), and others are conjectured to do so. This article systematically studies---for various classes of polymorphisms---the computational complexity of deciding whether or not a given structure H admits a polymorphism from the class. Among other results, we prove the NP-completeness of deciding a condition conjectured to characterize the tractable problems CSP(H), as well as the NP-completeness of deciding if CSP(H) has bounded width.