LIMIT BEHAVIOR OF LOCALLY CONSISTENT CONSTRAINT SATISFACTION PROBLEMS

BODIRSKY, M and Daniel KRÁĽ. LIMIT BEHAVIOR OF LOCALLY CONSISTENT CONSTRAINT SATISFACTION PROBLEMS. SIAM Journal on Discrete Mathematics. Philadelphia: SIAM, 2011, vol. 25, No 2, p. 916-933. ISSN 0895-4801. Available from: https://doi.org/10.1137/060667591.

Basic information

Original name

LIMIT BEHAVIOR OF LOCALLY CONSISTENT CONSTRAINT SATISFACTION PROBLEMS

Authors

BODIRSKY, M and Daniel KRÁĽ

Edition

SIAM Journal on Discrete Mathematics, Philadelphia, SIAM, 2011, 0895-4801

---

Other information

Language

English

Type of outcome

Article in a journal

Confidentiality degree

is not subject to a state or trade secret

Impact factor

Impact factor: 0.648

DOI

https://doi.org/10.1137/060667591

UT WoS

000292302000030

Keywords in English

constraint satisfaction problem (CSP); local consistency

---

Abstract

In the original language

An instance of a constraint satisfaction problem (CSP) is variable k-consistent if any sub-instance with at most k variables has a solution. For a fixed constraint language L, rho(k)(L) is the largest ratio such that any variable k-consistent instance has a solution that satisfies at least a fraction of rho(k)(L) of the constraints. We provide an expression for the limit rho(L) (sic) lim(k ->infinity)(L), and show that this limit coincides with the corresponding limit for constraint k-consistent instances, i.e., instances where all subinstances with at most k constraints have a solution. We also design an algorithm running in time polynomial in the size of input and 1/epsilon that for an input instance and a given e either computes a solution that satisfies at least a fraction of rho(L) - epsilon constraints or finds a set of inconsistent constraints whose size depends only on.. Most of our results apply both to weighted and to unweighted instances of the CSP.