Algebra Seminar talk
2026-03-06
Žaneta Semanišinova
How duality helps to understand resilience
Abstract:
A recent research topic in database theory is the computational complexity of resilience of queries. For a fixed conjunctive query, the problem is to compute the minimal number of facts that need to be removed from a given database so that it does not satisfy the query. Thanks to the existence of homomorphism duals for conjunctive queries, resilience problems can be viewed as valued constraint satisfaction problems (VCSPs) of structures that are finite or at least finite-like (in the sense that they have an oligomorphic automorphism group). This allows us to use complexity results and algebraic tools for VCSPs to understand the complexity of resilience problems. We present several complexity results for resilience problems obtained from this connection, including recent results for queries over a signature consisting of a single binary relation, so-called digraph queries. In this setting, the resilience problem for a digraph query q translates to a graph problem: given a directed multigraph G, compute the minimal number of edges to be removed so that G does not satisfy q. We show that the resilience problem for a digraph query is always in P or NP-complete.
This talk is based on joint work with Manuel Bodirsky and Carsten Lutz.