×

Binary constraint satisfaction problems defined by excluded topological minors. (English) Zbl 1408.68130

Summary: The binary Constraint Satisfaction Problem (CSP) is to decide whether there exists an assignment to a set of variables which satisfies specified constraints between pairs of variables. A binary CSP instance can be presented as a labelled graph encoding both the forms of the constraints and where they are imposed. We consider subproblems defined by restricting the allowed form of this graph. One type of restriction is to forbid certain specified substructures (patterns). This captures some tractable classes of the CSP, but does not capture classes defined by language restrictions, or the well-known structural property of acyclicity.
We extend the notion of pattern and introduce the notion of a topological minor of a binary CSP instance. By forbidding a finite set of patterns from occurring as topological minors we obtain a compact mechanism for expressing novel tractable subproblems of the CSP, including new generalisations of the class of acyclic instances.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
05C83 Graph minors
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI arXiv Link

References:

[1] Arnborg, S.; Proskurowski, A.; Corneil, D. G., Forbidden minors characterization of partial 3-trees, Discrete Math., 80, 1, 1-19, (1990) · Zbl 0701.05016
[2] Barto, L., Constraint satisfaction problem and universal algebra, ACM SIGLOG News, 1, 2, 14-24, (2014)
[3] Broersma, H.; Li, X.; Woeginger, G.; Zhang, S., Paths and cycles in colored graphs, Australas. J. Comb., 31, 299-311, (2005) · Zbl 1061.05030
[4] Bulatov, A., A dichotomy theorem for nonuniform CSP, (Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS’17), (2017), IEEE), 319-330
[5] Bulatov, A.; Krokhin, A.; Jeavons, P., Classifying the complexity of constraints using finite algebras, SIAM J. Comput., 34, 3, 720-742, (2005) · Zbl 1071.08002
[6] Cohen, D., A new hybrid class for which arc-consistency is a decision procedure, (Proceedings of 9th International Conference on Principles and Practice of Constraint Programming (CP’03). Proceedings of 9th International Conference on Principles and Practice of Constraint Programming (CP’03), Lecture Notes in Computer Science, vol. 2833, (2003), Springer-Verlag), 807-811 · Zbl 1273.68341
[7] Cohen, D. A.; Cooper, M. C.; Creed, P.; Marx, D.; Salamon, A. Z., The tractability of CSP classes defined by forbidden patterns, J. Artif. Intell. Res., 45, 47-78, (2012) · Zbl 1253.68296
[8] Cohen, D. A.; Cooper, M. C.; Escamoche, G.; Živný, S., Variable and value elimination in binary constraint satisfaction via forbidden patterns, J. Comput. Syst. Sci., 81, 7, 1127-1143, (2015) · Zbl 1320.68168
[9] Cohen, D. A.; Cooper, M. C.; Jeavons, P.; Živný, S., Tractable classes of binary CSPs defined by excluded topological minors, (Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI’15), (2015), AAAI Press), 1945-1951
[10] Cohen, D. A.; Jeavons, P. G., The power of propagation: when GAC is enough, Constraints, 22, 1, 3-23, (2017) · Zbl 1387.90130
[11] Cooper, M. C., An optimal k-consistency algorithm, Artif. Intell., 41, 89-95, (1989) · Zbl 0678.68058
[12] Cooper, M. C.; Escamocher, G., Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns, Discrete Appl. Math., 184, 89-113, (2015) · Zbl 1311.05004
[13] Cooper, M. C.; Jeavons, P. G.; Salamon, A. Z., Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination, Artif. Intell., 174, 9-10, 570-584, (2010) · Zbl 1205.68372
[14] Cooper, M. C.; Živný, S., Hybrid tractability of valued constraint problems, Artif. Intell., 175, 9-10, 1555-1569, (2011) · Zbl 1225.68243
[15] Cooper, M. C.; Živný, S., Hybrid tractable classes of constraint problems, (Krokhin, A.; Živný, S., Complexity and Approximability of Constraint Satisfaction Problems. Complexity and Approximability of Constraint Satisfaction Problems, Dagstuhl Follow-Ups, vol. 7, (2017), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), 113-135
[16] Cooper, M. C.; Živný, S., The power of arc consistency for CSPs defined by partially-ordered forbidden patterns, Log. Methods Comput. Sci., 13, 4, (2017) · Zbl 1387.68117
[17] Dalmau, V.; Kolaitis, P. G.; Vardi, M. Y., Constraint satisfaction, bounded treewidth, and finite-variable logics, (Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming (CP’02). Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming (CP’02), Lecture Notes in Computer Science, vol. 2470, (2002), Springer), 310-326
[18] Dechter, R., Constraint Processing, (2003), Morgan Kaufmann
[19] Dechter, R.; Pearl, J., Tree clustering for constraint networks, Artif. Intell., 38, 353-366, (1989) · Zbl 0665.68084
[20] Diestel, R., Graph Theory, (2010), Springer · Zbl 1204.05001
[21] Dirac, G. A., Short proof of Menger’s graph theorem, Mathematika, 13, 1, 42-44, (1966) · Zbl 0144.45102
[22] Downey, R.; Fellows, M., Parametrized Complexity, (1999), Springer · Zbl 0943.68079
[23] Escamocher, G., Forbidden Patterns in Constraint Satisfaction Problems, (2014), IRIT, University of Toulouse, Ph.D thesis
[24] 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
[25] Flum, J.; Grohe, M., Parametrized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series, (2006), Springer · Zbl 1143.68016
[26] Freuder, E., A sufficient condition for backtrack-free search, J. ACM, 29, 1, 24-32, (1982) · Zbl 0477.68063
[27] Freuder, E., A sufficient condition for backtrack-bounded search, J. ACM, 32, 4, 755-761, (1985) · Zbl 0633.68096
[28] Grohe, M., The complexity of homomorphism and constraint satisfaction problems seen from the other side, J. ACM, 54, 1, 1-24, (2007) · Zbl 1312.68101
[29] Grohe, M.; Kawarabayashi, K.; Marx, D.; Wollan, P., Finding topological subgraphs is fixed-parameter tractable, (Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC’11), (2011)), 479-488 · Zbl 1288.05058
[30] Hell, P.; Nešetřil, J., Colouring, constraint satisfaction, and complexity, Comput. Sci. Rev., 2, 3, 143-163, (2008) · Zbl 1302.68251
[31] Hopcroft, J. E.; Tarjan, R. E., Dividing a graph into triconnected components, SIAM J. Comput., 2, 3, 135-158, (1973) · Zbl 0281.05111
[32] Jeavons, P.; Cohen, D. A.; Gyssens, M., Closure properties of constraints, J. ACM, 44, 4, 527-548, (1997) · Zbl 0890.68064
[33] Jégou, P., Decomposition of domains based on the micro-structure of finite constraint-satisfaction problems, (Proceedings of the 11th National Conference on Artificial Intelligence (AAAI’93), (1993), AAAI Press), 731-736
[34] Kun, G.; Nešetřil, J., Forbidden lifts (NP and CSP for combinatorialists), Eur. J. Comb., 29, 4, 930-945, (2008) · Zbl 1213.68323
[35] Li, X.; Zhang, S.; Broersma, H., Paths and cycles in colored graphs, Electron. Notes Discrete Math., 8, 128-132, (2001) · Zbl 1412.05070
[36] Madelaine, F. R.; Stewart, I. A., Constraint satisfaction, logic and forbidden patterns, SIAM J. Comput., 37, 1, 132-163, (2007) · Zbl 1142.68035
[37] Marx, D., Tractable hypergraph properties for constraint satisfaction and conjunctive queries, J. ACM, 60, 6, (2013) · Zbl 1281.68135
[38] Robertson, N.; Seymour, P. D., Graph minors. V. Excluding a planar graph, J. Comb. Theory, Ser. B, 41, 1, 92-114, (1986) · Zbl 0598.05055
[39] Robertson, N.; Seymour, P. D., Graph minors. XX. Wagner’s conjecture, J. Comb. Theory, Ser. B, 92, 2, 325-357, (2004) · Zbl 1061.05088
[40] (Rossi, F.; van Beek, P.; Walsh, T., The Handbook of Constraint Programming, (2006), Elsevier) · Zbl 1175.90011
[41] Rossi, F.; Dahr, V.; Petrie, C., On the equivalence of constraint satisfaction problems, (Proceedings of the European Conference on Artificial Intelligence (ECAI90), (1990)), 550-556
[42] Tutte, W. T., Connectivity in Graphs, (1966), University of Toronto Press · Zbl 0146.45603
[43] Zhuk, D., The proof of CSP dichotomy conjecture, (Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS’17), (2017), IEEE), 331-342
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.