Locally Consistent Constraint Satisfaction Problems with Binary Constraints
Please always quote using this URN:urn:nbn:de:0296-matheon-2770
- 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.
Author: | Manuel Bodirsky, Dan Kral |
---|---|
URN: | urn:nbn:de:0296-matheon-2770 |
Referee: | Hans Jürgen Prömel |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2005/05/11 |
Release Date: | 2005/10/31 |
Institute: | Humboldt-Universität zu Berlin |
Preprint Number: | 279 |