The Complexity of Resilience Problems via Valued Constraint Satisfaction Problems
Article No.: 14, Pages 1 - 14
Abstract
Valued constraint satisfaction problems (VCSPs) constitute a large class of computational optimisation problems. It was shown recently that, over finite domains, every VCSP is in P or NP-complete, depending on the admitted cost functions. In this article, we study cost functions over countably infinite domains whose automorphisms form an oligomorphic permutation group. Our results include a hardness condition based on a generalisation of pp-constructability as known from classical CSPs and a polynomial-time tractability condition based on the concept of fractional polymorphisms. We then observe that the resilience problem for unions of conjunctive queries (UCQs) studied in database theory, under bag semantics, may be viewed as a special case of the VCSPs that we consider. We obtain a complexity dichotomy for the case of incidence-acyclic UCQs and exemplarily use our methods to determine the complexity of a query that had remained open in the literature. Further, we conjecture that our hardness and tractability conditions match for resilience problems for UCQs.
References
[1]
Nikhil Bansal, Avrim Blum, and Shuchi Chawla. 2004. Correlation clustering. Machine Learning 56, 1-3 (2004), 89--113.
[2]
Libor Barto, Jakub Opršal, and Michael Pinsker. 2018. The wonderland of reflections. Israel Journal of Mathematics 223, 1 (2018), 363--398.
[3]
Manuel Bodirsky. 2021. Complexity of Infinite-Domain Constraint Satisfaction. Cambridge University Press.
[4]
Manuel Bodirsky and Bertalan Bodor. 2024. A Complexity Dichotomy in Spatial Reasoning via Ramsey Theory. ACM Trans. Comput. Theory (mar 2024). Just Accepted.
[5]
Manuel Bodirsky and Jan Kára. 2008. The Complexity of Equality Constraint Languages. Theory of Computing Systems 3, 2 (2008), 136--158. A conference version appeared in the proceedings of Computer Science Russia (CSR'06).
[6]
Manuel Bodirsky, Florent Madelaine, and Antoine Mottet. 2018. A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP. In Proceedings of the Symposium on Logic in Computer Science (LICS). 105--114. Preprint arXiv:1802.03255.
[7]
Manuel Bodirsky, Marcello Mamino, and Caterina Viola. 2022. Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation. ACM Transactions of Computational Logic 23, 1 (2022), 1--35. Preprint arXiv:1912.09298.
[8]
Manuel Bodirsky and Antoine Mottet. 2018. A Dichotomy for First-Order Reducts of Unary Structures. Logical Methods in Computer Science 14, 2 (2018).
[9]
Manuel Bodirsky and Jaroslav Nešetřil. 2003. Constraint Satisfaction with Countable Homogeneous Templates. In Proceedings of Computer Science Logic (CSL). Vienna, 44--57.
[10]
Manuel Bodirsky, Michael Pinsker, and András Pongrácz. 2021. Projective clone homomorphisms. Journal of Symbolic Logic 86, 1 (2021), 148--161.
[11]
Manuel Bodirsky, Žaneta Semanišinová, and Carsten Lutz. 2023. The Complexity of Resilience Problems via Valued Constraint Satisfaction Problems. arXiv:2309.15654 [math.LO]
[12]
Andrei A. Bulatov. 2017. A Dichotomy Theorem for Nonuniform CSPs. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17. 319--330.
[13]
Peter J. Cameron. 1990. Oligomorphic permutation groups. Cambridge University Press, Cambridge.
[14]
Surajit Chaudhuri and Moshe Y. Vardi. 1993. Optimization of Real Conjunctive Queries. In Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (Washington, D.C., USA) (PODS '93). Association for Computing Machinery, New York, NY, USA, 59--70.
[15]
Gregory Cherlin, Saharon Shelah, and Niangdong Shi. 1999. Universal graphs with forbidden subgraphs and algebraic closure. Advances in Applied Mathematics 22 (1999), 454--491.
[16]
David A. Cohen, Martin C. Cooper, Páidí Creed, Peter G. Jeavons, and Stanislav Živný. 2013. An Algebraic Theory of Complexity for Discrete Optimization. SIAM J. Comput. 42, 5 (2013), 1915--1939.
[17]
David A. Cohen, Martin C. Cooper, and Peter Jeavons. 2006. An Algebraic Characterisation of Complexity for Valued Constraints. In Principles and Practice of Constraint Programming - CP 2006, 12th International Conference, CP 2006, Nantes, France, September 25-29, 2006, Proceedings. 107--121.
[18]
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms (1st ed.). Springer Publishing Company, Incorporated.
[19]
Jan Foniok. 2007. Homomorphisms and Structural Properties of Relational Systems. Doctoral Thesis, Charles University Prague, Faculty of Mathematics and Physics.
[20]
Cibele Freire, Wolfgang Gatterbauer, Neil Immerman, and Alexandra Meliou. 2015. A Characterization of the Complexity of Resilience and Responsibility for Self-join-free Conjunctive Queries. CoRR abs/1507.00674 (2015). arXiv:1507.00674 http://arxiv.org/abs/1507.00674
[21]
Cibele Freire, Wolfgang Gatterbauer, Neil Immerman, and Alexandra Meliou. 2015. The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries. Proc. VLDB Endow. 9, 3 (2015), 180--191.
[22]
Cibele Freire, Wolfgang Gatterbauer, Neil Immerman, and Alexandra Meliou. 2020. New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020. 271--284.
[23]
Peter Fulla and Stanislav Živný. 2016. A Galois Connection for Weighted (Relational) Clones of Infinite Size. TOCT 8, 3 (2016), 9:1--9:21.
[24]
Michael Garey and David Johnson. 1978. A guide to NP-completeness. CSLI Press, Stanford.
[25]
Wilfrid Hodges. 1997. A shorter model theory. Cambridge University Press, Cambridge.
[26]
Jan Hubička and Jaroslav Nešetřil. 2015. Universal Structures with Forbidden Homomorphisms. In Logic Without Borders - Essays on Set Theory, Model Theory, Philosophical Logic and Philosophy of Mathematics. De Gruyter, 241--264. arXiv:0907.4079.
[27]
Jan Hubička and Jaroslav Nešetřil. 2016. Homomorphism and Embedding Universal Structures for Restricted Classes. Multiple-Valued Logic and Soft Computing 27, 2-3 (2016), 229--253. arXiv:0909.4939.
[28]
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström. 2021. Solving hard cut problems via flow-augmentation. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021. 149--168.
[29]
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström. 2022. Directed flow-augmentation. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022. 938--947.
[30]
Vladimir Kolmogorov. 2019. Testing the Complexity of a Valued CSP Language. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 132). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 77:1--77:12.
[31]
Vladimir Kolmogorov, Andrei A. Krokhin, and Michal Rolinek. 2017. The Complexity of General-Valued CSPs. SIAM J. Comput. 46, 3 (2017), 1087--1110.
[32]
Vladimir Kolmogorov, Johan Thapper, and Stanislav Živný. 2015. The Power of Linear Programming for General-Valued CSPs. SIAM J. Comput. 44, 1 (2015), 1--36.
[33]
Marcin Kozik and Joanna Ochremiak. 2015. Algebraic Properties of Valued Constraint Satisfaction Problem. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I. 846--858.
[34]
Andrei Krokhin and Stanislav Živný. 2017. The Complexity of Valued CSPs. In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav Zivny (Eds.). Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 233--266.
[35]
Benoit Larose, Cynthia Loten, and Claude Tardif. 2007. A Characterisation of First-Order Constraint Satisfaction Problems. Logical Methods in Computer Science 3, 4:6 (2007).
[36]
Neha Makhija and Wolfgang Gatterbauer. 2023. A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations. Proc. ACM Manag. Data 1, 4, Article 228 (dec 2023), 27 pages.
[37]
Alexandra Meliou, Wolfgang Gatterbauer, Katherine F. Moore, and Dan Suciu. 2010. The Complexity of Causality and Responsibility for Query Answers and non-Answers. Proc. VLDB Endow. 4, 1 (2010), 34--45.
[38]
Antoine Mottet and Michael Pinsker. 2020. Smooth Approximations and CSPs over finitely bounded homogeneous structures. (2020). Preprint arXiv:2011.03978.
[39]
Jaroslav Nešetřil and Claude Tardif. 2000. Duality theorems for finite structures. Journal of Combinatorial Theory, Series B 80 (2000), 80--97.
[40]
Friedrich Martin Schneider and Caterina Viola. 2022. An Application of Farkas' Lemma to Finite-Valued Constraint Satisfaction Problems over Infinite Domains. CoRR abs/2208.04912 (2022). arXiv:2208.04912
[41]
Johan Thapper and Stanislav Živný. 2013. The complexity of finite-valued CSPs. In Proceedings of the Symposium on Theory of Computing Conference (STOC), Palo Alto, CA, USA, June 1-4, 2013. 695--704.
[42]
Caterina Viola. 2020. Valued Constraint Satisfaction Problems over Infinite Domains. Ph. D. Dissertation. TU Dresden.
[43]
Caterina Viola and Stanislav Živný. 2021. The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains. ACM Trans. Algorithms 17, 3 (2021), 21:1--21:23.
[44]
Dmitriy Zhuk. 2020. A Proof of the CSP Dichotomy Conjecture. J. ACM 67, 5 (2020), 30:1--30:78.
[45]
Dmitriy N. Zhuk. 2017. A Proof of CSP Dichotomy Conjecture. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17. 331--342. https://arxiv.org/abs/1704.01914.
Index Terms
- The Complexity of Resilience Problems via Valued Constraint Satisfaction Problems
Recommendations
Hard constraint satisfaction problems have hard gaps at location 1
An instance of the maximum constraint satisfaction problem (Max CSP) is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constraints. Max CSP captures many ...
Parameterized complexity of constraint satisfaction problems
We prove a parameterized analog of Schaefer's Dichotomy Theorem: we show that for every finite boolean constraint family , deciding whether a formula containing constraints from has a satisfying assignment of weight exactly k is either fixed-parameter ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2024
988 pages
ISBN:9798400706608
DOI:10.1145/3661814
- Conference Chair:
- Pawel Sobocinski,
- Program Chairs:
- Ugo Dal Lago,
- Javier Esparza
This work is licensed under a Creative Commons Attribution-ShareAlike International 4.0 License.
Sponsors
- SIGLOG: ACM Special Interest Group on Logic and Computation
- IEEE Computer Society
In-Cooperation
- EACSL
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 08 July 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
LICS '24
Sponsor:
LICS '24: 39th Annual ACM/IEEE Symposium on Logic in Computer Science
July 8 - 11, 2024
Tallinn, Estonia
Acceptance Rates
LICS '24 Paper Acceptance Rate 72 of 236 submissions, 31%;
Overall Acceptance Rate 215 of 622 submissions, 35%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 54Total Downloads
- Downloads (Last 12 months)54
- Downloads (Last 6 weeks)30
Reflects downloads up to 23 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in