×

On the speed of constraint propagation and the time complexity of arc consistency testing. (English) Zbl 1378.68059

Summary: Establishing arc consistency on two relational structures is one of the most popular heuristics for the constraint satisfaction problem. We aim at determining the time complexity of arc consistency testing. The input structures \(G\) and \(H\) can be supposed to be connected colored graphs, as the general problem reduces to this particular case. We first observe the upper bound \(O(e(G) v(H) + v(G) e(H))\), which implies the bound \(O(e(G) e(H))\) in terms of the number of edges and the bound \(O((v(G) + v(H))^3)\) in terms of the number of vertices. We then show that both bounds are tight as long as an arc consistency algorithm is based on constraint propagation (as all current algorithms are). Our lower bounds are based on examples of slow constraint propagation. We measure the speed of constraint propagation observed on a pair \(G\), \(H\) by the size of a combinatorial proof that Spoiler wins the existential 2-pebble game on \(G\), \(H\).

MSC:

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Feder, T.; Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory, SIAM J. Comput., 28, 1, 57-104 (1998) · Zbl 0914.68075
[2] Berkholz, C., Lower bounds for existential pebble games and \(k\)-consistency tests, Log. Methods Comput. Sci., 9, 4, 1-23 (2013) · Zbl 1297.68088
[3] Mackworth, A. K., Consistency in networks of relations, Artif. Intell., 8, 1, 99-118 (1977) · Zbl 0341.68061
[4] Bessière, C., Handbook of Constraint Programming, 29-84 (2006), Elsevier: Elsevier Amsterdam, Ch. Constraint Propagation
[5] Dongen, M. R.C.v., AC-3d an efficient arc-consistency algorithm with a low space-complexity, (Proc. Principles and Practice of Constraint Programming 2002. Proc. Principles and Practice of Constraint Programming 2002, CP’02. Proc. Principles and Practice of Constraint Programming 2002. Proc. Principles and Practice of Constraint Programming 2002, CP’02, LNCS, vol. 2470 (2002), Springer: Springer Heidelberg), 755-760
[6] Mohr, R.; Henderson, T. C., Arc and path consistency revisited, Artif. Intell., 28, 2, 225-233 (1986)
[7] Hentenryck, P. V.; Deville, Y.; Teng, C.-M., A generic arc-consistency algorithm and its specializations, Artif. Intell., 57, 291-321 (1992) · Zbl 0763.68059
[8] Bessière, C., Arc-consistency and arc-consistency again, Artif. Intell., 65, 1, 179-190 (1994)
[9] Bessière, C.; Freuder, E. C.; Regin, J.-C., Using constraint metaknowledge to reduce arc consistency computation, Artif. Intell., 107, 1, 125-148 (1999) · Zbl 0911.68192
[10] Chmeiss, A.; Jegou, P., Efficient path-consistency propagation, Int. J. Artif. Intell. Tools, 07, 02, 121-142 (1998)
[11] Régin, J.-C., AC-*: a configurable, generic and adaptive arc consistency algorithm, (van Beek, P., Principles and Practice of Constraint Programming 2005. Principles and Practice of Constraint Programming 2005, CP’05. Principles and Practice of Constraint Programming 2005. Principles and Practice of Constraint Programming 2005, CP’05, LNCS, vol. 3709 (2005), Springer: Springer Heidelberg), 505-519 · Zbl 1153.68480
[12] Kolaitis, P. G.; Vardi, M. Y., On the expressive power of datalog: tools and a case study, J. Comput. Syst. Sci., 51, 1, 110-134 (1995) · Zbl 1360.68397
[13] Kolaitis, P. G.; Vardi, M. Y., A game-theoretic approach to constraint satisfaction, (Kautz, H. A.; Porter, B. W., AAAI/IAAI 2000 (2000), AAAI Press/The MIT Press: AAAI Press/The MIT Press California), 175-181
[14] Kolaitis, P. G.; Panttaja, J., On the complexity of existential pebble games, (Baaz, M.; Makowsky, J. A., Computer Science Logic 2003. Computer Science Logic 2003, CSL 2003. Computer Science Logic 2003. Computer Science Logic 2003, CSL 2003, LNCS, vol. 2803 (2003), Springer: Springer Heidelberg), 314-329 · Zbl 1116.68474
[15] Atserias, A.; Bulatov, A. A.; Dalmau, V., On the power of k -consistency, (Arge, L.; Cachin, C.; Jurdzinski, T.; Tarlecki, A., ICALP 2007. ICALP 2007, LNCS, vol. 4596 (2007), Springer: Springer Heidelberg), 279-290 · Zbl 1171.68720
[16] Atserias, A.; Dalmau, V., A combinatorial characterization of resolution width, J. Comput. Syst. Sci., 74, 3, 323-334 (2008) · Zbl 1133.03034
[17] Berkholz, C., On the complexity of finding narrow proofs, (FOCS 2012 (2012), IEEE Computer Society: IEEE Computer Society Los Alamitos, CA, USA), 351-360
[18] Dechter, R.; Pearl, J., A Problem Simplification Approach that Generates Heuristics for Constraint-Satisfaction Problems (1985), Cognitive Systems Laboratory, Computer Science Department, University of California: Cognitive Systems Laboratory, Computer Science Department, University of California Los Angeles, Tech. rep. · Zbl 0678.68100
[19] Samal, A.; Henderson, T., Parallel consistent labeling algorithms, Int. J. Parallel Program., 16, 341-364 (1987) · Zbl 0646.68104
[20] Bessière, C.; Régin, J.-C.; Yap, R. H.C.; Zhang, Y., An optimal coarse-grained arc consistency algorithm, Artif. Intell., 165, 2, 165-185 (2005) · Zbl 1132.68691
[21] Berkholz, C.; Verbitsky, O., On the speed of constraint propagation and the time complexity of arc consistency testing, (Chatterjee, K.; Sgall, J., Proceedings, Mathematical Foundations of Computer Science 2013. Proceedings, Mathematical Foundations of Computer Science 2013, MFCS’13. Proceedings, Mathematical Foundations of Computer Science 2013. Proceedings, Mathematical Foundations of Computer Science 2013, MFCS’13, LNCS, vol. 8087 (2013), Springer), 159-170 · Zbl 1378.68058
[22] Baker, R.; Harman, G.; Pintz, J., The difference between consecutive primes. II, Proc. Lond. Math. Soc., Ser. III, 83, 3, 532-562 (2001) · Zbl 1016.11037
[23] Berkholz, C.; Krebs, A.; Verbitsky, O., Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy, ACM Trans. Comput. Log., 16, 3, 21:1-21:26 (2015) · Zbl 1354.03038
[24] Atserias, A.; Kolaitis, P.; Vardi, M., Constraint propagation as a proof system, (Wallace, M., Principles and Practice of Constraint Programming 2004. Principles and Practice of Constraint Programming 2004, CP’04. Principles and Practice of Constraint Programming 2004. Principles and Practice of Constraint Programming 2004, CP’04, LNCS, vol. 3258 (2004), Springer: Springer Heidelberg), 77-91 · Zbl 1152.68537
[25] Kasif, S., On the parallel complexity of discrete relaxation in constraint satisfaction networks, Artif. Intell., 45, 3, 275-286 (1990) · Zbl 0717.68043
[26] McConnell, R. M.; Mehlhorn, K.; Näher, S.; Schweitzer, P., Certifying algorithms, Comput. Sci. Rev., 5, 2, 119-161 (2011) · Zbl 1298.68289
[27] Berkholz, C., The propagation depth of local consistency, (Proceedings of the 20th International Conference on Principles and Practice of Constraint Programming. Proceedings of the 20th International Conference on Principles and Practice of Constraint Programming, CP 2014 (2014)), 158-173
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.