The Complexity of Resilience for Digraph Queries
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909985465696256 |
|---|---|
| author | Bodirsky, Manuel Semanišinová, Žaneta |
| author_facet | Bodirsky, Manuel Semanišinová, Žaneta |
| contents | 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\}$ of directed graphs). Specifically, for every union $μ$ of conjunctive digraph queries, the following problem is in P or NP-complete: given a directed multigraph $G$ and a natural number $u$, can we remove $u$ edges from $G$ so that $G \models \neg μ$? In fact, we verify a more general dichotomy conjecture from (Bodirsky et al., 2024) for all resilience problems in the special case of directed graphs, and show that for such unions of queries $μ$ there exists a countably infinite ('dual') valued structure $Δ_μ$ which either primitively positively constructs 1-in-3-3-SAT, and hence the resilience problem for $μ$ is NP-complete by general principles, or has a pseudo cyclic canonical fractional polymorphism, and the resilience problem for $μ$ is in P. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_05346 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Complexity of Resilience for Digraph Queries Bodirsky, Manuel Semanišinová, Žaneta Logic Computational Complexity Databases 68P15, 68Q25, 68R10, 08A70 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\}$ of directed graphs). Specifically, for every union $μ$ of conjunctive digraph queries, the following problem is in P or NP-complete: given a directed multigraph $G$ and a natural number $u$, can we remove $u$ edges from $G$ so that $G \models \neg μ$? In fact, we verify a more general dichotomy conjecture from (Bodirsky et al., 2024) for all resilience problems in the special case of directed graphs, and show that for such unions of queries $μ$ there exists a countably infinite ('dual') valued structure $Δ_μ$ which either primitively positively constructs 1-in-3-3-SAT, and hence the resilience problem for $μ$ is NP-complete by general principles, or has a pseudo cyclic canonical fractional polymorphism, and the resilience problem for $μ$ is in P. |
| title | The Complexity of Resilience for Digraph Queries |
| topic | Logic Computational Complexity Databases 68P15, 68Q25, 68R10, 08A70 |
| url | https://arxiv.org/abs/2601.05346 |