{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:37:28Z","timestamp":1787323048004,"version":"build-2736575974"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2011,1,1]]},"abstract":"<jats:p>An instance of a constraint satisfaction problem (CSP) is variable [Formula: see text]- consistent if any subinstance with at most [Formula: see text] variables has a solution. For a fixed constraint language [Formula: see text], [Formula: see text] is the largest ratio such that any variable [Formula: see text]-consistent instance has a solution that satisfies at least a fraction of [Formula: see text] of the constraints. We provide an expression for the limit [Formula: see text], and show that this limit coincides with the corresponding limit for constraint [Formula: see text]- consistent instances, i.e., instances where all subinstances with at most [Formula: see text] constraints have a solution. We also design an algorithm running in time polynomial in the size of input and [Formula: see text] that for an input instance and a given [Formula: see text] either computes a solution that satisfies at least a fraction of [Formula: see text] constraints or finds a set of inconsistent constraints whose size depends only on [Formula: see text]. Most of our results apply both to weighted and to unweighted instances of the CSP.<\/jats:p>","DOI":"10.1137\/060667591","type":"journal-article","created":{"date-parts":[[2011,7,4]],"date-time":"2011-07-04T19:46:26Z","timestamp":1309808786000},"page":"916-933","source":"Crossref","is-referenced-by-count":0,"title":["Limit Behavior of Locally Consistent Constraint Satisfaction Problems"],"prefix":"10.1137","volume":"25","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Kr\u00e1l\u2019","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,7,1]]},"reference":[{"key":"R1","unstructured":"M.   Bodirsky   and  \n                            D.   Kr\u00e1l\u2019   , Locally consistent constraint satisfaction problems with binary constraints\n                    , in\n                      Proceedings of the 31th Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201905)\n                      , Lecture Notes in Comput. Sci                     .  3787 , Springer-Verlag                     , Berlin                     ,  2005 , pp.\u00a0                     295 \u2013 306 ."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"R3","unstructured":"S.   Cook   and  \n                            D.   Mitchell   , Finding hard instances of the satisfiability problem: A survey\n                    , in\n                      The Satisfiability Problem: Theory and Applications\n                      , DIMACS Ser. Discrete Math. Theoret. Comput. Sci                     .  35 , AMS                     , Providence, RI                     ,  1997 , pp.\u00a0                     1 \u2013 17 ."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.3011"},{"key":"R5","unstructured":"V.   Dalmau   and  \n                            J.   Pearson   , Closure functions and width 1 problems\n                    , in\n                      Proceedings of the 5th International Conference on Principles and Practice of Constraint Programming (CP)\n                      , Lecture Notes in Comput. Sci                     .  1713 , Springer-Verlag                     , Berlin                     ,  1999 , pp.\u00a0                     159 \u2013 173 ."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)86737-0"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(89)90037-4"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.012"},{"key":"R8","unstructured":"A preliminary version appeared in\n                      Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP)\n                      , Lecture Notes in Comput. Sci                     .  3142 , Springer-Verlag                     , Berlin                     ,  2004 , pp.\u00a0                     469 \u2013 480 ."},{"key":"R9","unstructured":"D.   Eppstein   , Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction\n                    , in                       Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA) , SIAM                     , Philadelphia, PA                     ,  2001 , pp.\u00a0                     329 \u2013 337 ."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00224-9"},{"key":"R11","unstructured":"T.   Feder   and  \n                            M.   Vardi   , Monotone monadic SNP and constraint satisfaction\n                    , in                       Proceedings of the 25th Symposium on Theory of Computing (STOC) ,  1993 , pp.\u00a0                     612 \u2013 622 ."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/322290.322292"},{"key":"R14","unstructured":"E. C.   Freuder   , Complexity of K-tree structured constraint satisfaction problems\n                    , in                       Proceedings of the 8th National Conference on Artificial Intelligence , AAAI                     ,  1990 , pp.\u00a0                     4 \u2013 9 ."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90214-I"},{"key":"R16","unstructured":"P.   Hell   and  \n                            J.   Ne\u0161et\u0159il   ,\n                      Graphs and Homomorphisms\n                      , Oxford University Press\n                    , Oxford, UK                     ,  2004 ."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-96-01537-1"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90166-5"},{"key":"R19","unstructured":"S.   Janson  ,  \n                            T.   \u0141uczak   and  \n                            A.   Ruci\u0144ski   ,\n                      Random Graphs\n                      , Wiley & Sons\n                    , New York                     ,  2000 ."},{"key":"R20","unstructured":"S.   Jukna   ,\n                      Extremal Combinatorics with Applications in Computer Science\n                      , Springer-Verlag\n                    , Heidelberg                     ,  2001 ."},{"key":"R21","unstructured":"Ph. G.   Kolaitis   and  \n                            M. Y.   Vardi   , Conjunctive-query containment and constraint satisfaction\n                    , in                       Proceedings of the 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS\u201998) , ACM                     , New York, pp.\u00a0                     205 \u2013 213 ."},{"key":"R22","unstructured":"D.   Kr\u00e1l\u2019   , Locally satisfiable formulas\n                    , in\n                      Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA)\n                      , SIAM                     , Philadelphia, PA                     ,  2004 , pp.\u00a0                     323 \u2013 332 ."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.012"},{"key":"R23","unstructured":"A preliminary version appeared in\n                      Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS)\n                      , Lecture Notes in Comput. Sci                     .  3618 , Springer-Verlag                     , Berlin                     ,  2005 , pp.\u00a0                     603 \u2013 614 ."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-3(4:6)2007"},{"key":"R24","unstructured":"available online from                      http:\/\/arxiv.org\/PS_cache\/arxiv\/pdf\/0707\/0707.2562v2.pdf                     ."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1145\/322248.322260"},{"key":"R26","unstructured":"K.   Lieberherr   and  \n                            E.   Specker   ,  Complexity of Partial Satisfaction II ,  Technical report 293 , Department of EECS, Princeton University, Princeton, NJ\n                    ,  1982 ."},{"key":"R27","unstructured":"R.   Motwani   and  \n                            P.   Raghavan   ,\n                      Randomized Algorithms\n                      , Cambridge University Press\n                    , Cambridge, UK                     ,  1995 ."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197326528"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177703585"},{"key":"R30","unstructured":"G. J.   Woeginger   , Exact Algorithms for NP-hard Problems: A Survey\n                    , in\n                      Proceedings of the 5th International Workshop Combinatorial Optimization\u2014Eureka, You Shrink\n                      , Lecture Notes in Comput. Sci                     .  2570 , Springer-Verlag                     , Berlin                     ,  2003 , pp.\u00a0                     185 \u2013 207 ."},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1045"},{"key":"R31","unstructured":"A preliminary version appeared in\n                      Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , SIAM                     , Philadelphia, PA                     ,  1992 , pp.\u00a0                     1 \u2013 9 ."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060667591","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:39:04Z","timestamp":1787319544000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060667591"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,1]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,1,1]]}},"alternative-id":["10.1137\/060667591"],"URL":"https:\/\/doi.org\/10.1137\/060667591","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1,1]]}}}