Weak consistency notions for all the CSPs of bounded width

ABSTRACT

The characterization of all the Constraint Satisfaction Problems of bounded width, proposed by Feder and Vardi [SICOMP'98], was confirmed in [Bulatov'09] and independently in [FOCS'09, JACM'14]. Both proofs are based on the (2,3)-consistency (using Prague consistency in [FOCS'09], directly in [Bulatov'09]) which is costly to verify.

We introduce a new consistency notion, Singleton Linear Arc Consistency (SLAC), and show that it solves the same family of problems. SLAC is weaker than Singleton Arc Consistency (SAC) and thus the result answers the question from [JLC'13] by showing that SAC solves all the problems of bounded width. At the same time the problem of verifying weaker consistency (even SAC) offers significant computational advantages over the problem of verifying (2,3)-consistency which improves the algorithms solving the CSPs of bounded width.

References

1. L. Barto. The collapse of the bounded width hierarchy. Journal of Logic and Computation, 2014. doi: 10.1093/logcom/exu070.
2. L. Barto and M. Kozik. Constraint Satisfaction Problems of bounded width. In Foundations of Computer Science, 2009. FOCS '09. 50th Annual IEEE Symposium on, pages 595--603, Oct 2009. doi: 10.1109/FOCS.2009.32.
3. L. Barto and M. Kozik. New conditions for Taylor varieties and CSP. In Logic in Computer Science (LICS), 2010 25th Annual IEEE Symposium on, pages 100--109, July 2010. doi: 10.1109/LICS.2010.34.
4. L. Barto and M. Kozik. Robust satisfiability of Constraint Satisfaction Problems. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC '12, pages 931--940, New York, NY, USA, 2012. ACM. ISBN 978-1-4503-1245-5. doi: 10.1145/2213977.2214061.
5. L. Barto and M. Kozik. Constraint Satisfaction Problems solvable by local consistency methods. J. ACM, 61(1):3:1--3:19, Jan. 2014. ISSN 0004-5411. doi: 10.1145/2556646.
6. L. Barto, M. Kozik, and R. Willard. Near unanimity constraints have bounded pathwidth duality. In Proceedings of the 2012 27th Annual IEEE/ACM Symposium on Logic in Computer Science, LICS '12, pages 125--134, Washington, DC, USA, 2012. IEEE Computer Society. ISBN 978-0-7695-4769-5. doi: 10.1109/LICS.2012.24.
7. C. Bessiere and R. Debruyne. Theoretical analysis of singleton arc consistency and its extensions. Artificial Intelligence, 172(1):29--41, 2008. ISSN 0004-3702. doi: http://dx.doi.org/10.1016/j.artint.2007.09.001.
8. M. Bodirsky and H. Chen. Peek arc consistency. Theoretical Computer Science, 411(2):445--453, 2010. ISSN 0304-3975. doi: http://dx.doi.org/10.1016/j.tcs.2009.07.059.
9. V.G. Bodnarčuk, L.A. Kalužnin, V.N. Kotov, and B.A. Romov. Galois theory for Post algebras. I, II. Kibernetika (Kiev), (3):1--10; ibid. 1969, no. 5, 1--9, 1969. ISSN 0023-1274.
10. A. Bulatov. Bounded relational width. 2009. manuscript.
11. A. Bulatov, P. Jeavons, and A. Krokhin. Classifying the complexity of constraints using finite algebras. SIAM J. Comput., 34:720--742, March 2005. ISSN 0097-5397. doi: http://dx.doi.org/10.1137/S0097539700376676.
12. A. A. Bulatov, A. A. Krokhin, and P. Jeavons. Constraint satisfaction problems and finite algebras. In Automata, languages and programming (Geneva, 2000), volume 1853 of Lecture Notes in Comput. Sci., pages 272--282. Springer, Berlin, 2000.
13. H. Chen, V. Dalmau, and B. Grußien. Arc consistency and friends. Journal of Logic and Computation, 23(1):87--108, 2013. doi: 10.1093/logcom/exr039.
14. V. Dalmau and A. Krokhin. Majority constraints have bounded pathwidth duality. European Journal of Combinatorics, 29(4):821--837, 2008. ISSN 0195-6698. doi: http://dx.doi.org/10.1016/j.ejc.2007.11.020. Homomorphisms: Structure and Highlights Homomorphisms: Structure and Highlights.
15. V. Dalmau and A. Krokhin. Robust satisfiability for CSPs: Hardness and algorithmic results. ACM Trans. Comput. Theory, 5(4):15:1--15:25, Nov. 2013. ISSN 1942-3454. doi: 10.1145/2540090.
16. V. Dalmau and J. Pearson. Closure functions and width 1 problems. In J. Jaffar, editor, Principles and Practice of Constraint Programming - CP'99, volume 1713 of Lecture Notes in Computer Science, pages 159--173. Springer Berlin Heidelberg, 1999. ISBN 978-3-540-66626-4. doi: 10.1007/978-3-540-48085-3_12.
17. R. Debruyne and C. Bessiere. Some practicable filtering techniques for the Constraint Satisfaction Problem. In In Proceedings of IJCAI'97, pages 412--417, 1997.
18. T. Feder and M. Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal on Computing, 28(1):57--104, 1998. doi: 10.1137/S0097539794266766.
19. V. Guruswami and Y. Zhou. Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set. In D. Randall, editor, SODA, pages 1574--1589. SIAM, 2011.
20. B. Larose and L. Zádori. Bounded width problems and algebras. Algebra universalis, 56(3-4):439--466, 2007. ISSN 0002-5240. doi: 10.1007/s00012-007-2012-6.

Index Terms

• Theory of computation

  • Logic

    • Constraint and logic programming