Determining the Number of Solutions to Binary CSP Instances
2002 (English)In: Principles and Practice of Constraint Programming, 8th International Conference CP-2002,2002, Heidelberg: Springer Verlag , 2002, p. 327-Conference paper, Published paper (Refereed)
Abstract [en]
Counting the number of solutions to CSP instances has applications in several areas, ranging from statistical physics to artificial intelligence. We give an algorithm for counting the number of solutions to binary CSPs, which works by transforming the problem into a number of 2-SAT instances, where the total number of solutions to these instances is the same as those of the original problem. The algorithm consists of two main cases, depending on whether the domain size d is even, in which case the algorithm runs in O(1.3247^n*(d/2)^n) time, or odd, in which case it runs in O(1.3247^n*((d^2+d+2)/4)^(n/2)) if d=4*k+1, and O(1.3247^n*((d^2+d)/4)^(n/2)) if d=4*k+3. We also give an algorithm for counting the number of possible 3-colourings of a given graph, which runs in O(1.8171^n), an improvement over our general algorithm gained by using problem specific knowledge.
Place, publisher, year, edition, pages
Heidelberg: Springer Verlag , 2002. p. 327-
Keywords [en]
Tvärvetenskap, constraint satisfaction, counting problems, CSP
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-24612Local ID: 6788OAI: oai:DiVA.org:liu-24612DiVA, id: diva2:244934
2009-10-072009-10-072018-01-13