Locally consistent constraint satisfaction problems with binary constraints

BODIRSKY, M a Daniel KRÁĽ. Locally consistent constraint satisfaction problems with binary constraints. GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE. BERLIN: SPRINGER-VERLAG BERLIN, 2005, roč. 3787, s. 295-306. ISSN 0302-9743.

Základní údaje

Originální název

Locally consistent constraint satisfaction problems with binary constraints

Autoři

BODIRSKY, M a Daniel KRÁĽ

Vydání

GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, BERLIN, SPRINGER-VERLAG BERLIN, 2005, 0302-9743

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

UT WoS

000234875500026

---

Anotace

V originále

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.