3 papers
math.LO2026
The Complexity of Resilience for Digraph Queries
Manuel Bodirsky, Žaneta Semanišinová
We prove a complexity dichotomy for the resilience problem for unions of conjunctive digraph queries (i.e., for existential positive sentences over the signature of directe…
cs.LO2024
Identifying Tractable Quantified Temporal Constraints within Ord-Horn
Jakub Rydval, Žaneta Semanišinová, Michał Wrona
The constraint satisfaction problem, parameterized by a relational structure, provides a general framework for expressing computational decision problems. Already the restriction t…
math.LO2023
The Complexity of Resilience Problems via Valued Constraint Satisfaction
Manuel Bodirsky, Žaneta Semanišinová, Carsten Lutz
Valued constraint satisfaction problems (VCSPs) constitute a large class of computational optimization problems. It was shown recently that, over finite domains, every VCSP is in P…