×

Backdoors into heterogeneous classes of SAT and CSP. (English) Zbl 1356.68097

Summary: In this paper we extend the classical notion of strong and weak backdoor sets for SAT and CSP by allowing that different instantiations of the backdoor variables result in instances that belong to different base classes; the union of the base classes forms a heterogeneous base class. Backdoor sets to heterogeneous base classes can be much smaller than backdoor sets to homogeneous ones, hence they are much more desirable but possibly harder to find. We draw a detailed complexity landscape for the problem of detecting strong and weak backdoor sets into heterogeneous base classes for SAT and CSP.

MSC:

68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Gaspers, S.; Misra, N.; Ordyniak, S.; Szeider, S.; Živný, S., Backdoors into heterogeneous classes of SAT and CSP, (Brodley, C. E.; Stone, P., Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27-31, 2014, Québec City, Québec, Canada (2014), AAAI Press), 2652-2658
[2] Williams, R.; Gomes, C.; Selman, B., Backdoors to typical case complexity, (Gottlob, G.; Walsh, T., Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI 2003 (2003), Morgan Kaufmann), 1173-1178
[3] Williams, R.; Gomes, C.; Selman, B., On the connections between backdoors, restarts, and heavy-tailedness in combinatorial search, (Informal Proc. of the Sixth International Conference on Theory and Applications of Satisfiability Testing, SAT 2003. Informal Proc. of the Sixth International Conference on Theory and Applications of Satisfiability Testing, SAT 2003, 5-8 May 2003 (2003), S. Margherita Ligure, Portofino: S. Margherita Ligure, Portofino Italy), 222-230
[4] Ruan, Y.; Kautz, H. A.; Horvitz, E., The backdoor key: a path to understanding problem hardness, (McGuinness, D. L.; Ferguson, G., Proceedings of the 19th National Conference on Artificial Intelligence. Proceedings of the 19th National Conference on Artificial Intelligence, 16th Conference on Innovative Applications of Artificial Intelligence (2004), AAAI Press/The MIT Press), 124-130
[5] Dilkina, B. N.; Gomes, C. P.; Sabharwal, A., Tradeoffs in the complexity of backdoor detection, (Proceedings of the 13th International Conference, Principles and Practice of Constraint Programming. Proceedings of the 13th International Conference, Principles and Practice of Constraint Programming, CP 2007, Providence, RI, USA, 23-27 September 2007. Proceedings of the 13th International Conference, Principles and Practice of Constraint Programming. Proceedings of the 13th International Conference, Principles and Practice of Constraint Programming, CP 2007, Providence, RI, USA, 23-27 September 2007, Lecture Notes in Computer Science, vol. 4741 (2007), Springer Verlag), 256-270 · Zbl 1145.68511
[6] Samer, M.; Szeider, S., Fixed-parameter tractability, (Biere, A.; Heule, M.; van Maaren, H.; Walsh, T., Handbook of Satisfiability (2009), IOS Press), 425-454, chap. 13
[7] Kottler, S.; Kaufmann, M.; Sinz, C., A new bound for an NP-hard subclass of 3-SAT using backdoors, (Büning, H. K.; Zhao, X., Proceedings of the 11th International Conference, Theory and Applications of Satisfiability Testing - SAT 2008. Proceedings of the 11th International Conference, Theory and Applications of Satisfiability Testing - SAT 2008, SAT 2008, Guangzhou, China, 12-15 May 2008. Proceedings of the 11th International Conference, Theory and Applications of Satisfiability Testing - SAT 2008. Proceedings of the 11th International Conference, Theory and Applications of Satisfiability Testing - SAT 2008, SAT 2008, Guangzhou, China, 12-15 May 2008, Lecture Notes in Computer Science, vol. 4996 (2008), Springer Verlag), 161-167 · Zbl 1138.68543
[8] Dilkina, B. N.; Gomes, C. P.; Sabharwal, A., Backdoors in the context of learning, (Kullmann, O., Proceedings of the 12th International Conference, Theory and Applications of Satisfiability Testing - SAT 2009. Proceedings of the 12th International Conference, Theory and Applications of Satisfiability Testing - SAT 2009, SAT 2009, Swansea, UK, June 30-July 3, 2009. Proceedings of the 12th International Conference, Theory and Applications of Satisfiability Testing - SAT 2009. Proceedings of the 12th International Conference, Theory and Applications of Satisfiability Testing - SAT 2009, SAT 2009, Swansea, UK, June 30-July 3, 2009, Lecture Notes in Computer Science, vol. 5584 (2009), Springer Verlag), 73-79 · Zbl 1247.68250
[9] Gaspers, S.; Szeider, S., Strong backdoors to bounded treewidth SAT, (54th Annual IEEE Symposium on Foundations of Computer Science. 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October 2013, Berkeley, CA, USA (2013), IEEE Computer Society), 489-498
[10] LeBras, R.; Bernstein, R.; Gomes, C. P.; Selman, B.; van Dover, R. B., Crowdsourcing backdoor identification for combinatorial optimization, (Rossi, F., Proceedings of the 23rd International Joint Conference on Artificial Intelligence. Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, 3-9 August 2013 (2013), IJCAI/AAAI), 2840-2847
[11] Pfandler, A.; Rümmele, S.; Szeider, S., Backdoors to abduction, (Rossi, F., Proceedings of the 23rd International Joint Conference on Artificial Intelligence, IJCAI 2013. Proceedings of the 23rd International Joint Conference on Artificial Intelligence, IJCAI 2013, Beijing, China, 3-9 August 2013 (2013), IJCAI/AAAI), 1046-1052
[12] Dvorák, W.; Ordyniak, S.; Szeider, S., Augmenting tractable fragments of abstract argumentation, Artif. Intell., 186, 157-173 (2012) · Zbl 1251.68225
[13] Samer, M.; Szeider, S., Backdoor sets of quantified Boolean formulas, J. Autom. Reason., 42, 1, 77-97 (2009) · Zbl 1191.68353
[14] Kronegger, M.; Ordyniak, S.; Pfandler, A., Backdoors to planning, (Brodley, C. E.; Stone, P., Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 27-31 July 2014, Québec City, Québec, Canada (2014), AAAI Press), 2300-2307
[15] Kronegger, M.; Ordyniak, S.; Pfandler, A., Variable-deletion backdoors to planning, (Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 25-30 January 2015, Austin Texas, Austin, USA (2014), AAAI Press), 2300-2307
[16] Downey, R. G.; Fellows, M. R., Fundamentals of Parameterized Complexity, Texts in Computer Science (2013), Springer Verlag · Zbl 1358.68006
[17] Nishimura, N.; Ragde, P.; Szeider, S., Detecting backdoor sets with respect to Horn and binary clauses, (Proceedings of Seventh International Conference on Theory and Applications of Satisfiability Testing. Proceedings of Seventh International Conference on Theory and Applications of Satisfiability Testing, SAT 2004, 10-13 May 2004, Vancouver, BC, Canada (2004)), 96-103
[18] Gaspers, S.; Szeider, S., Backdoors to satisfaction, (Bodlaender, H. L.; Downey, R.; Fomin, F. V.; Marx, D., The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, Lecture Notes in Computer Science, vol. 7370 (2012), Springer Verlag), 287-317 · Zbl 1358.68133
[19] Schaefer, T. J., The complexity of satisfiability problems, (Conference Record of the Tenth Annual ACM Symposium on Theory of Computing. Conference Record of the Tenth Annual ACM Symposium on Theory of Computing, San Diego, Calif., 1978 (1978), ACM), 216-226 · Zbl 1282.68143
[20] Bulatov, A. A.; Dalmau, V., A simple algorithm for Mal’tsev constraints, SIAM J. Comput., 36, 1, 16-27 (2006) · Zbl 1112.08002
[21] Idziak, P. M.; Markovic, P.; McKenzie, R.; Valeriote, M.; Willard, R., Tractability and learnability arising from algebras with few subpowers, SIAM J. Comput., 39, 7, 3023-3037 (2010) · Zbl 1216.68129
[22] Barto, L.; Kozik, M., Constraint satisfaction problems solvable by local consistency methods, J. ACM, 61, 1, Article 3 pp. (2014) · Zbl 1295.68126
[23] Jeavons, P.; Cohen, D.; Gyssens, M., Closure properties of constraints, J. ACM, 44, 4, 527-548 (1997) · Zbl 0890.68064
[24] Barto, L., Constraint satisfaction problem and universal algebra, ACM SIGLOG News, 1, 2, 14-24 (2014)
[25] Carbonnel, C.; Cooper, M. C.; Hebrard, E., On backdoors to tractable constraint languages, (O’Sullivan, B., Proceedings of the 20th International Conference, Principles and Practice of Constraint Programming. Proceedings of the 20th International Conference, Principles and Practice of Constraint Programming, CP 2014, Lyon, France, 8-12 September 2014. Proceedings of the 20th International Conference, Principles and Practice of Constraint Programming. Proceedings of the 20th International Conference, Principles and Practice of Constraint Programming, CP 2014, Lyon, France, 8-12 September 2014, Lecture Notes in Computer Science, vol. 8656 (2014), Springer), 224-239
[26] Ganian, R.; Ramanujan, M. S.; Szeider, S., Discovering archipelagos of tractability for constraint satisfaction and counting, (Krautamer, R., Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, 10-12 January 2016 (2016), SIAM), 1670-1681 · Zbl 1410.68166
[27] Carbonnel, C.; Cooper, M. C., Tractability in constraint satisfaction problems: a survey, Constraints, 21, 2, 115-144 (2016) · Zbl 1334.90220
[28] Knuth, D. E., The Art of Computer Programming, vol. IVa: Combinatorial Algorithms, Part 1 (2011), Addison-Wesley
[29] Szeider, S., Matched formulas and backdoor sets, J. Satisf. Boolean Model. Comput., 6, 1-12 (2008) · Zbl 1187.68254
[30] Jeavons, P.; Cohen, D. A.; Cooper, M. C., Constraints, consistency and closure, Artif. Intell., 101, 1-2, 251-265 (1998) · Zbl 0909.68076
[31] 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
[32] Idziak, P. M.; Markovic, P.; McKenzie, R.; Valeriote, M.; Willard, R., Tractability and learnability arising from algebras with few subpowers, SIAM J. Comput., 39, 7, 3023-3037 (2010) · Zbl 1216.68129
[33] Kozik, M.; Krokhin, A.; Valeriote, M.; Willard, R., Characterizations of several Maltsev Conditions, Algebra Univers., 73, 3-4, 205-224 (2015) · Zbl 1319.08002
[34] Barto, L.; Kozik, M., Constraint satisfaction problems solvable by local consistency methods, J. ACM, 61, 1, 3:1-3:19 (2014) · Zbl 1295.68126
[35] Bessiere, C.; Carbonnel, C.; Hebrard, E.; Katsirelos, G.; Walsh, T., Detecting and exploiting subproblem tractability, (Rossi, F., Proceedings of the 23rd International Joint Conference on Artificial Intelligence. Proceedings of the 23rd International Joint Conference on Artificial Intelligence, IJCAI 2013, Beijing, China, 3-9 August 2013 (2013), IJCAI/AAAI), 468-474
[36] Samer, M.; Szeider, S., Constraint satisfaction with bounded treewidth revisited, J. Comput. Syst. Sci., 76, 2, 103-114 (2010) · Zbl 1186.68443
[37] Gottlob, G.; Leone, N.; Scarcello, F., Hypertree decompositions and tractable queries, J. Comput. Syst. Sci., 64, 3, 579-627 (2002) · Zbl 1052.68025
[38] 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
[39] Eiben, E.; Ganian, R.; Szeider, S., Meta-kernelization using well-structured modulators, (Husfeldt, T.; Kanj, I. A., 10th International Symposium, Parameterized and Exact Computation. 10th International Symposium, Parameterized and Exact Computation, IPEC 2014, Patras, Greece, September 16-18, 2015. 10th International Symposium, Parameterized and Exact Computation. 10th International Symposium, Parameterized and Exact Computation, IPEC 2014, Patras, Greece, September 16-18, 2015, LIPIcs, vol. 43 (2015)), 114-126, Revised Selected Papers · Zbl 1378.68073
[40] Eiben, E.; Ganian, R.; Szeider, S., Solving problems on graphs of high rank-width, (Algorithms and Data Structures Symposium, WADS 2015. Algorithms and Data Structures Symposium, WADS 2015, 5-7 August 2015, University of Victoria, BC, Canada. Algorithms and Data Structures Symposium, WADS 2015. Algorithms and Data Structures Symposium, WADS 2015, 5-7 August 2015, University of Victoria, BC, Canada, LNCS (2015), Springer Verlag), 314-326, URL: · Zbl 1392.68199
[41] Ganian, R.; Ramanujan, M. S.; Szeider, S., Combining treewidth and backdoors for CSP, CoRR (2016), abs/1610.03298, URL: · Zbl 1402.68094
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.