×

A polynomial relational class of binary CSP. (English) Zbl 1484.68071

Summary: Finding a solution to a constraint satisfaction problem (CSP) is known to be an NP-hard task. Considerable effort has been spent on identifying tractable classes of CSP, in other words, classes of constraint satisfaction problems for which there are polynomial time recognition and resolution algorithms. In this article, we present a relational tractable class of binary CSP. Our key contribution is a new ternary operation that we name mjx. We first characterize mjx-closed relations which leads to an optimal algorithm to recognize such relations. To reduce space and time complexity, we define a new storage technique for these relations which reduces the complexity of establishing a form of strong directional path consistency, the consistency level that solves all instances of the proposed class (and, indeed, of all relational classes closed under a majority polymorphism).

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q27 Parameterized complexity, tractability and kernelization
68R07 Computational aspects of satisfiability
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Bessiere, C., Carbonnel, C., Hebrard, E., Katsirelos, G., Detecting, T.W.: Detecting and exploiting subproblem tractability. In: Rossi, F. (ed.) IJCAI 2013 Proceedings of the 23rd International Joint Conference on Artificial Intelligence. IJCAI/AAAI, Beijing (2013)
[2] Bulatov, AA; Jeavons, PG; Krokhin, AA, Classifying the complexity of constraints using finite algebras, SIAM J. Comput., 34, 720-742, (2005) · Zbl 1071.08002 · doi:10.1137/S0097539700376676
[3] Barto, L; Kozik, M, Constraint satisfaction problems solvable by local consistency methods, J. ACM, 61, 3, (2014) · Zbl 1295.68126 · doi:10.1145/2556646
[4] Barto, L., Kozik, M., Willard, R.: Near unanimity constraints have bounded pathwidth duality. In: LICS, pp. 125-134. IEEE (2012) · Zbl 1362.68095
[5] Bessière, C; Régin, J-C; Yap, RHC; Zhang, Y, An optimal coarse-grained arc consistency algorithm, Artif. Intell., 165, 165-185, (2005) · Zbl 1132.68691 · doi:10.1016/j.artint.2005.02.004
[6] Carbonnel, C; Cooper, MC, Tractability in constraint satisfaction problems: A survey, Constraints, 21, 115-144, (2016) · Zbl 1334.90220 · doi:10.1007/s10601-015-9198-6
[7] Chen, H; Dalmau, V; Grußien, B, Arc consistency and friends, J. Log. Comput., 23, 87-108, (2013) · Zbl 1282.68134 · doi:10.1093/logcom/exr039
[8] Cohen, D.A., Jeavons, P.G.: The complexity of constraint languages. In: Rossi, F, van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, pp 245-280. Elsevier, Amsterdam (2006) · Zbl 1183.68309
[9] Cooper, MC; Jeavons, PG; Salamon, AZ, Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination, Artif. Intell., 174, 570-584, (2010) · Zbl 1205.68372 · doi:10.1016/j.artint.2010.03.002
[10] Cooper, M.C., Mouelhi, A., El, Terrioux, C., Zanuttini, B.: On broken triangles. In: O’Sullivan, B. (ed.) Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Lyon, France, September 8-12 Proceedings, Volume 8656 of Lecture Notes in Computer Science, pp 9-24. Springer, Berlin (2014) · Zbl 0633.68096
[11] Cooper, MC, An optimal k-consistency algorithm, Artif. Intell., 41, 89-95, (1989) · Zbl 0678.68058 · doi:10.1016/0004-3702(89)90080-5
[12] Deville, Y; Barette, O; Van Hentenryck. P, Constraint satisfaction over connected row convex constraints, Artif. Intell., 109, 243-271, (1999) · Zbl 0916.68061 · doi:10.1016/S0004-3702(99)00012-0
[13] Dechter, R.: Constraint Processing. Morgan Kaufmann Publishers Inc., San Francisco (2003) · Zbl 1057.68114
[14] Dechter, R; Pearl, J, Network-based heuristics for constraint-satisfaction problems, Artif Intell., 34, 1-38, (1987) · Zbl 0643.68156 · doi:10.1016/0004-3702(87)90002-6
[15] Freuder, EC, A sufficient condition for backtrack-bounded search, J. ACM, 32, 755-761, (1985) · Zbl 0633.68096 · doi:10.1145/4221.4225
[16] Feder, T; Vardi, MY, The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM, J. Comput., 28, 57-104, (1998) · Zbl 0914.68075
[17] Green, MJ; Cohen, DA, Domain permutation reduction for constraint satisfaction problems, Artif. Intell., 172, 1094-1118, (2008) · Zbl 1183.68309 · doi:10.1016/j.artint.2007.12.001
[18] Gottlob, G; Leone, N; Scarcello, F, A comparison of structural CSP decomposition methods, Artif. Intell., 124, 243-282, (2000) · Zbl 0952.68044 · doi:10.1016/S0004-3702(00)00078-3
[19] Grohe, M, The complexity of homomorphism and constraint satisfaction problems seen from the other side, J. ACM, 54, 1-24, (2007) · Zbl 1312.68101 · doi:10.1145/1206035.1206036
[20] Jeavons, P; Cooper, M, Tractable constraints on ordered domains, Artif. Intell., 79, 327-339, (1995) · Zbl 1013.68503 · doi:10.1016/0004-3702(95)00107-7
[21] Jeavons, P; Cohen, DA; Cooper, MC, Constraints, consistency and closure, Artif. Intell., 101, 251-265, (1998) · Zbl 0909.68076 · doi:10.1016/S0004-3702(98)00022-8
[22] Jeavons, PG, On the algebraic structure of combinatorial problems, Theor. Comput. Sci., 200, 185-204, (1998) · Zbl 0915.68074 · doi:10.1016/S0304-3975(97)00230-2
[23] Naanaa, W, Unifying and extending hybrid tractable classes of csps, J. Exp. Theor. Artif Intell., 25, 407-424, (2013) · doi:10.1080/0952813X.2012.721138
[24] van Hoeve, W.-J., Katriel, I.: Global constraints. In: Rossi, F, van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, Volume 2 of Foundations of Artificial Intelligence, pp 169-208. Elsevier, Amsterdam (2006)
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.