Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
CSP vượt ra ngoài các ngôn ngữ ràng buộc có thể giải được
Tóm tắt
Vấn đề thỏa mãn ràng buộc (CSP) là một trong những vấn đề tính toán được nghiên cứu nhiều nhất. Mặc dù thuộc loại NP-khó, nhiều tiểu vấn đề có thể giải được đã được xác định (Bulatov 2017, Zhuk 2017). Các backdoor, được giới thiệu bởi Williams, Gomes và Selman (2003), dần mở rộng lớp có thể giải được này tới tất cả các trường hợp CSP cách lớp đó một khoảng cách nhất định. Quy mô backdoor cung cấp một thước đo khoảng cách tự nhiên nhưng khá thô giữa một trường hợp CSP và một lớp có thể giải được. Độ sâu backdoor, được giới thiệu bởi Mählmann, Siebertz và Vigny (2021) cho SAT, là một thước đo khoảng cách tinh vi hơn, cho phép sử dụng song song các biến backdoor khác nhau. Quy mô backdoor có giới hạn suy ra độ sâu backdoor có giới hạn, nhưng có những trường hợp có độ sâu backdoor hằng số và quy mô backdoor tùy ý lớn. Dreier, Ordyniak và Szeider (2022) đã cung cấp các thuật toán tham số cố định để tìm các backdoor có độ sâu nhỏ vào các lớp công thức Horn và Krom. Trong bài báo này, chúng tôi xem xét độ sâu backdoor cho CSP. Chúng tôi xem xét các backdoor liên quan đến các tiểu vấn đề có thể giải được $$C_\Gamma $$ của CSP được xác định bởi một ngôn ngữ ràng buộc $$\varvec{\Gamma }$$, tức là nơi tất cả các ràng buộc đều sử dụng các quan hệ từ ngôn ngữ $$\varvec{\Gamma }$$. Dựa trên phương pháp lý thuyết trò chơi của Dreier và các khái niệm về cản trở phân tách của họ, chúng tôi chỉ ra rằng đối với mọi ngôn ngữ ràng buộc hữu hạn, có thể giải được và bán bảo tồn $$\varvec{\Gamma }$$, CSP là có thể giải được với tham số cố định được tham số hóa theo độ sâu backdoor vào $$C_{\varvec{\Gamma }}$$ cộng với kích thước miền. Với các backdoor có độ sâu thấp, chúng tôi đạt tới các lớp trường hợp cần backdoor với quy mô tùy ý lớn. Do đó, kết quả của chúng tôi thực sự tổng quát hóa một số kết quả đã biết cho CSP dựa trên quy mô backdoor.
Từ khóa
#vấn đề thỏa mãn ràng buộc #backdoor #độ sâu backdoor #thuật toán tham số cố định #ngôn ngữ ràng buộc có thể giải đượcTài liệu tham khảo
Carbonnel, C., & Cooper, M. C. (2016). Tractability in constraint satisfaction problems: a survey. Constraints, 21(2), 115–144.
Bulatov, A.A. (2017). A dichotomy theorem for nonuniform CSPs. In C. Umans (Ed.), 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, (pp. 319–330). IEEE Computer Society. https://doi.org/10.1109/FOCS.2017.37.
Cooper, M. C., Cohen, D. A., & Jeavons, P. (1994). Characterising tractable constraints. Artificial Intelligence, 65(2), 347–361. https://doi.org/10.1016/0004-3702(94)90021-3.
Cohen, D., & Jeavons, P. (2006). The complexity of constraint languages. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of Constraint Programming (8th ed., Vol. I, pp. 245–280). Elsevier.
Schaefer, T.J. (1978). The complexity of satisfiability problems. In Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, Calif., 1978), (pp. 216–226). ACM.
Zhuk, D. (2017). A proof of CSP dichotomy conjecture. In C. Umans (Ed.), 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017 (pp. 331–342). IEEE Computer Society. https://doi.org/10.1109/FOCS.2017.38.
Cohen, D., Jeavons, P., & Gyssens, M. (2005). A unified theory of structural tractability for constraint satisfaction and spread cut decomposition. In International Joint Conferences on Artificial Intelligence (IJCAI-05), (pp. 72–77).
Gottlob, G., Leone, N., & Scarcello, F. (2000). A comparison of structural CSP decomposition methods. Artificial Intelligence, 124(2), 243–282.
Gottlob, G., Leone, N., & Scarcello, F. (2002). Hypertree decompositions and tractable queries. J. of Computer and System Sciences, 64(3), 579–627.
Cohen, D. A., Cooper, M. C., Creed, P., Marx, D., & Salamon, A. Z. (2012). The tractability of CSP classes defined by forbidden patterns. J. Artif. Intell. Res., 45, 47–78.
Cooper, M. .C., Jégou, P., & Terrioux, C. (2015). A microstructure-based family of tractable classes for CSPs. In G. Pesant (Ed.), Principles and Practice of Constraint Programming - 21st International Conference, CP 2015, Proceedings, Lecture Notes in Computer Science (Vol. 9255, pp. 74–88). Springer Verlag.
Cohen, D.A., Cooper, M.C., Jeavons, P.G., & Zivný, S. (2015). Tractable classes of binary CSPs defined by excluded topological minors. In Q. Yang, & M. J. Wooldridge (Eds.), Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015 (pp. 1945–1951). AAAI Press.
Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., & Saurabh, S. (2015). Parameterized Algorithms. Springer.
Downey, R.G., & Fellows, M.R. (2013) Fundamentals of parameterized complexity. Texts in computer science. Springer Verlag.
Flum, J., & Grohe, M. (2006). Parameterized complexity theory, Texts in theoretical computer science. An EATCS series (vol. XIV). Berlin: Springer Verlag.
Niedermeier, R. (2006). Invitation to fixed-parameter algorithms. Oxford lecture series in mathematics and its applications. Oxford: Oxford University Press.
Samer, M., & Szeider, S. (2021). Fixed-parameter tractability. In A. Biere, H. van Maaren, & T. Walsh (Eds.), Handbook of Satisfiability (2nd ed., Vol. 17, pp. 693–736). IOS Press. https://doi.org/10.3233/FAIA201000.
Williams, R., Gomes, C., & Selman, B. (2003). Backdoors to typical case complexity. In G. Gottlob, & T. Walsh (Eds.), Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI 2003 (pp. 1173–1178). Morgan Kaufmann.
Williams, R., Gomes, C., & Selman, B. (2003). On the connections between backdoors, restarts, and heavy-tailedness in combinatorial search. In Informal Proc. of the Sixth International Conference on Theory and Applications of Satisfiability Testing, S. Margherita Ligure - Portofino, Italy, May 5-8, 2003 (pp. 222–230). SAT.
Samer, M., Szeider, S. (2008). Backdoor trees. In AAAI 08, Twenty-Third Conference on Artificial Intelligence, Chicago, Illinois, July 13–17, 2008 (pp. 363–368). AAAI Press.
Ordyniak, S., Schidler, A., & Szeider, S. (2021). Backdoor DNFs. In Z. Zhou (Ed.), Proceeding of IJCAI-2021, the 30th International Joint Conference on Artificial Intelligence (pp. 1403–1409). https://doi.org/10.24963/ijcai.2021/194.
Mählmann, N., Siebertz, S., & Vigny, A. (2021). Recursive backdoors for SAT. In F. Bonchi, & S. J. Puglisi (Eds.), 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, LIPIcs (Vol. 202, p. 73:1–73:18). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2021.73.
Nesetril, J., & de Mendez, P. O. (2006). Tree-depth, subgraph coloring and homomorphism bounds. European J. Combin., 27(6), 1022–1041.
Nešetřil, J., & de Mendez, P.O. (2012). Sparsity - graphs, structures, and algorithms, algorithms and combinatorics (vol. 28). Springer.
Bulian, J., & Dawar, A. (2016). Graph isomorphism parameterized by elimination distance to bounded degree. Algorithmica, 75(2), 363–382.
Fomin, F.V., Golovach, P.A., & Thilikos, D.M. (2021). Parameterized complexity of elimination distance to first-order logic properties. arXiv:2104.02998.
Dreier, J., Ordyniak, S., & Szeider, S. (2022). SAT backdoors: Depth beats size. In S. Chechik, G. Navarro, E. Rotenberg, & G. Herman (Eds.), 30th Annual European Symposium on Algorithms, ESA 2022, LIPIcs, September 5-9, 2022, Berlin/Potsdam, Germany (vol. 244, pp. 46:1–46:18). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. arXiv:2202.08326.
Gaspers, S., Misra, N., Ordyniak, S., Szeider, S., & Zivny, S. (2017). Backdoors into heterogeneous classes of SAT and CSP. J. of Computer and System Sciences, 85, 38–56. https://doi.org/10.1016/j.jcss.2016.10.007.
Ganian, R., Ramanujan, M. S., & Szeider, S. (2017). Discovering archipelagos of tractability for constraint satisfaction and counting. ACM Transactions on Algorithms, 13(2), 29:1–29:32. https://doi.org/10.1145/3014587.
Ganian, R., Ramanujan, M. .S., & Szeider, S. (2017). Combining treewidth and backdoors for CSP. In H. Vollmer, & B. Vallée (Eds.), 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs) (Vol. 66, p. 36:1–36:17). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.STACS.2017.36.
Dreier, J., Ordyniak, S., & Szeider, S. (2022). CSP beyond tractable constraint languages. In C. Solnon (Ed.), 28th International Conference on Principles and Practice of Constraint Programming, CP 2022, July 31– August 8, 2022, Haifa, Israel, LIPIcs (vol. 235, pp. 20:1–20:17). Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Bulatov, A. A. (2011). Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Log., 12(4), 24:1–24:66. https://doi.org/10.1145/1970398.1970400.
Ganian, R., Ramanujan, M.S., & Szeider, S. (2016). Discovering archipelagos of tractability for constraint satisfaction and counting. In R. Krauthgamer (Ed.), Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016 (pp. 1670–1681). SIAM.
Bulatov, A. A. (2013). The complexity of the counting constraint satisfaction problem. J. of the ACM, 60(5), 34:1–34:41. https://doi.org/10.1145/2528400.