EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

The Complexity of Resilience Problems via Valued Constraint Satisfaction

Manuel Bodirsky, Žaneta Semanišinová, Carsten Lutz

ACM Transactions on Computational Logic · 31.07.2026 · 27 (3) · 1-59

DOI: 10.1145/3806207 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Computational Logic, online erschienen am 18.05.2026. Verfasst von Manuel Bodirsky und 2 weiteren Autor:innen. Die Arbeit nennt 66 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: European Research Council, DFG, Austrian Science Fund.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Valued Constraint Satisfaction Problems (VCSPs) constitute a large class of computational optimization problems. It was recently shown 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 generalization 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 conjunctive query that has been stated as an open problem in the literature. We conjecture that our hardness and tractability conditions match for resilience problems for UCQs. Further, we obtain a complete dichotomy for resilience problems for two-way regular path queries, under bag semantics.

Förderung

  • European Research Council
  • DFG
  • Austrian Science Fund

Zitieren

APA

Bodirsky, M., Semanišinová, Ž., & Lutz, C. (2026). The Complexity of Resilience Problems via Valued Constraint Satisfaction. ACM Transactions on Computational Logic, 27(3), 1-59. https://doi.org/10.1145/3806207

Vancouver

Bodirsky M, Semanišinová Ž, Lutz C. The Complexity of Resilience Problems via Valued Constraint Satisfaction. ACM Transactions on Computational Logic. 2026;27(3):1-59. doi:10.1145/3806207

BibTeX
@article{Bodirsky2026,
  author = {Bodirsky, Manuel and Semanišinová, Žaneta and Lutz, Carsten},
  title = {The Complexity of Resilience Problems via Valued Constraint Satisfaction},
  journal = {ACM Transactions on Computational Logic},
  year = {2026},
  volume = {27},
  number = {3},
  pages = {1--59},
  doi = {10.1145/3806207}
}
Kostenlos starten →