TY - GEN A1 - Bodirsky, Manuel A1 - Kral, Dan T1 - Locally Consistent Constraint Satisfaction Problems with Binary Constraints N2 - 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. Y1 - 2005 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/277 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-2770 ER -