The Complexity of Resilience for Digraph Queries
Manuel Bodirsky, Žaneta Semanišinová · 2026
Read The Complexity of Resilience for Digraph Queries by Manuel Bodirsky, Žaneta Semanišinová (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-05346.txt.
Introduction
Manuel Bodirsky and Žaneta Semanišinová prove a complexity dichotomy for the resilience problem on directed graph queries in a 2026 paper. Resilience asks how many edges must be removed from a directed graph so that a given query stops being satisfied, a measure of how robustly the data imply the query's answer. For every union of conjunctive digraph queries, they show the problem is either solvable in polynomial time or NP-complete, with nothing in between.
In doing so they verify, for directed graphs, a more general dichotomy conjecture about resilience problems from earlier work. A complete classification tells database theorists exactly which query shapes admit efficient resilience computation. That knowledge guides the design of data-cleaning tools that measure how fragile a database conclusion is.
Catalog record
| CREATOR | Manuel Bodirsky, Žaneta Semanišinová |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 105 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-05346
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Complexity of Resilience for Digraph Queries Manuel Bodirsky, Žaneta Semanišinová Abstract We prove a complexity dichotomy for the resilience problem for unions of conjunctive digraph queries (i.e., for existential positive sentences over the signature { R } \{R\} of directed graphs). Specifically, for every union μ \mu of conjunctive digraph queries, the following problem is in P or NP-complete: given a directed multigraph G G and a natural number u u , can we remove u u edges from G G so that G ⊧ ¬ μ G\models\neg\mu ? In fact, we verify a more general dichotomy conjecture from [ 3 ] for all resilience problems in the special case of directed graphs, and show that for such unions of queries μ \mu there exists a countably infinite (‘dual’) valued structure Δ μ \Delta_{\mu} which either primitively positively constructs 1-in-3-3-SAT, and hence the resilience problem for μ \mu is NP-complete by general principles, or has a pseudo cyclic canonical fractional polymorphism, and the resilience problem for μ \mu is in P. Institut für Algebra, TU Dresden, [email protected]://orcid.org/0000-0001-8228-3611The author has been funded by the European Research Council (Project POCOCOP, ERC Synergy Grant 101071674) and by the DFG (Project FinHom, Grant 467967530). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. Institute of Discrete Mathematics and Geometry, TU Wien, [email protected]://orcid.org/0000-0001-8111-0671The author has been funded by the European Research Council (Project POCOCOP, ERC Synergy Grant 101071674). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. This research was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/ESP6949724. ccs Theory of computation Problems, reductions and completeness ccs Theory of computation Complexity theory and logic ccs Theory of computation Database query processing and optimization (theory) keywords valued constraints, unions of conjunctive queries, resilience, computational complexity, pp-constructions † † runningauthor: M. Bodirsky and Ž. Semanišinová † † copyright: M. Bodirsky and Ž. Semanišinová † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction The resilience problem for a fixed conjunctive query, or more generally for a union of conjunctive queries \mu , is the problem of deciding for a given database {\mathfrak{A}} and u\in{\mathbb{N}} whether it is possible to remove at most u tuples from {\mathfrak{A}} so that {\mathfrak{A}} does not satisfy \mu . The resilience problem lies at the core of algorithmic challenges in various forms of reverse data management, where an action is required on the input data to achieve a desired outcome in the output data [ 18 ] . The computational complexity of this problem depends on the query \mu . The resilience problem is always in NP, and often NP-complete, but for some queries \mu the problem can be solved in polynomial time; see, e.g., [ 11 , 12 , 17 , 3 ] for some partial classification results. The computational complexity of the problem also depends on whether we view the database {\mathfrak{A}} under set semantics (i.e., {\mathfrak{A}} is treated as a relational structure) or under bag semantics (i.e., {\mathfrak{A}} is a structure where each tuple appears with some multiplicity), and both settings have been studied in the literature (in particular, see [ 3 , 17 ] for results in bag semantics). The importance of bag semantics stems from applications: bag databases represent SQL databases more faithfully. There are examples of conjunctive queries \mu for which the resilience problem in bag and set semantics have different complexities [ 17 ] . Recently, a connection between the resilience problem under bag semantics and valued constraint satisfaction has been established [ 3 ] . The connection is based on the fact that for every union of connected conjunctive queries \mu , the resilience problem in bag semantics is equal to a valued constraint satisfaction problem (VCSP) for some template dependent on \mu , and therefore the algebraic tools developed for describing the complexity of VCSPs can be utilized. To do so, we focus in this paper on the resilience problem exclusively under bag semantics and from now on, always implicitly assume this semantics for resilience problems. It has been conjectured that resilience problems exhibit a complexity dichotomy in the sense that all problems are NP-complete or in P [ 17 ] . This conjecture has been verified in some special cases, for instance if \mu is a conjunctive query which is self-join-free [ 17 ] , or if \mu is a union of conjunctive queries that are Berge-acyclic [ 3 ] . The proof of the latter is based on a connection to finite-domain VCSPs, which also covers resilience problems for regular path queries (RPQs), and even two-way RPQs. Resilience of (one-way) RPQs has also been studied recently in [ 1 ] where the authors present language-theoretic conditions for computational hardness. However, the conjecture in full generality remains open. In this article, we confirm the complexity dichotomy conjecture in the special case where the signature of the database consists of a single binary relation symbol R , that is, we prove the following: Theorem 1 . If \mu is a union of conjunctive queries over a binary signature \{R\} , then the resilience problem for \mu is in P or NP-complete. The class of unions of conjunctive queries over \{R\} is incomparable with the class of queries studied in [ 12 ] (in set semantics), since they study queries with arbitrary signatures, but with a single repetition of a single binary relation symbol. In the case that the signature is equal to \{R\} , the query expresses a directed graph property and the resilience problem can be phrased as follows: given a directed multigraph G and a natural number u , can we remove u edges from G so that G\models\neg\mu ? Edge-removal problems have been studied from a computational complexity perspective in the graph theory community as well, especially for concrete properties [ 14 , Section A1.2] . In [ 10 ] the authors study edge-removal problems for first-order logic properties in general; however, they only consider simple undirected graphs and study the problem from the perspective of parametrized complexity , where the number of edges that is removed is the parameter. The scope of our contribution extends beyond verifying the complexity dichotomy conjecture for digraph resilience problems: we also verify a variant of a stronger conjecture (from [ 3 ] ) which provides a precise mathematical condition aiming at predicting the border between NP-hardness and polynomial-time tractability, based on simulations of a hard Boolean constraint satisfaction problem (CSP) using so-called pp-constructions . This condition is one-sided correct in the sense that if