Locally Consistent Constraint Satisfaction Problems with Binary Constraints

Abstract

We study constraint satisfaction problems (CSPs) that are k-consistent in the sense that any k input constraints can be simultaneously satisfied. In this setting, we focus on constraint languages with a single binary constraint type. Such a constraint satisfaction problem is equivalent to the question whether there is a homomorphism from an input digraph G to a fixed target digraph H. The instance corresponding to G is k-consistent if every subgraph of G of size at most k is homomorphic to H. Let ρ _k (H) be the largest ρ such that every k-consistent G contains a subgraph G′ of size at least ρ ∥ E(G)∥ that is homomorphic to H. The ratio ρ _k (H) reflects the fraction of constraints of a k-consistent instance that can be always satisfied. We determine ρ _k (H) for all digraphs H that are not acyclic and show that lim _k→ ∞ ρ _k (H) = 1 if and only if H has tree duality. In addition, for graphs H with tree duality, we design an algorithm that computes in linear time for a given input graph G either a homomorphism from almost the entire graph G to H, or a subgraph of G of bounded size that is not homomorphic to H.