Locally consistent constraint satisfaction problems - (Extended abstract)

DVORAK, Z; Daniel KRÁĽ and O PANGRAC. Locally consistent constraint satisfaction problems - (Extended abstract). AUTOMATA , LANGUAGES AND PROGRAMMING, PROCEEDINGS. BERLIN: SPRINGER-VERLAG BERLIN, 2004, vol. 3142, p. 469-480. ISSN 0302-9743.

Basic information

Original name

Locally consistent constraint satisfaction problems - (Extended abstract)

Authors

DVORAK, Z; Daniel KRÁĽ and O PANGRAC

Edition

AUTOMATA , LANGUAGES AND PROGRAMMING, PROCEEDINGS, BERLIN, SPRINGER-VERLAG BERLIN, 2004, 0302-9743

---

Other information

Language

English

Type of outcome

Article in a journal

Confidentiality degree

is not subject to a state or trade secret

UT WoS

000223656400041

---

Abstract

In the original language

An instance of a constraint satisfaction problem is l-consistent if any l constraints of it can be simultaneously satisfied. For a fixed constraint type P, rho(l)(P) denotes the largest ratio of constraints which can be satisfied in any l-consistent instance. In this paper, we study locally consistent constraint satisfaction problems for constraints which are Boolean predicates. We determine the values of rho(l)(P) for all I and all Boolean predicates which have a certain natural property which we call 1-extendibility as well as for all Boolean predicates of arity at most three. All our results hold for both the unweighted and weighted versions of the problem.