Informace o publikaci
Locally consistent constraint satisfaction problems with binary constraints
| Autoři | |
|---|---|
| Rok publikování | 2005 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE |
| Citace | |
| Popis | 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 rho(k)(H) be the largest rho such that every k-consistent C contains a subgraph G' of size at least rho parallel to E(G)parallel to that is homomorphic to H. The ratio rho(k)(H) reflects the fraction of constraints of a k-consistent instance that can be always satisfied. We determine pk(H) for all digraphs H that axe not acyclic and show that lim(k -> infinity) rho(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 C 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. |