Open Access

Manuel Bodirsky, Dan Kral

• An instance of a constraint satisfaction problem is k-consistent if any k constraints of it can be simultaneously satisfied. We focus on constraint languages with a single binary constraint. In this case, the 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 r_k(H) be the largest r such that every k-consistent G contains a subgraph G' of size at least r ||E(G)|| that is homomorphic to H. The ratio r_k(H) reflects the fraction of constraints of a k-consistent instance that can be always satisfied. We determine r_k(H) for all digraphs H that are not acyclic and show that lim r_k(H)=1 for k tending to infinity if H has tree duality. For the latter case we design an efficient algorithm that computes in linear time for a given input graph G and epsilon>0 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.