2026-10-01T07:51:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25504 2026-09-23T23:42:08Z ddc:004 open_access

The Complexity of Resilience for Digraph Queries Bodirsky, Manuel Semanišinová, Žaneta valued constraints unions of conjunctive queries resilience computational complexity pp-constructions 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 ⊧ ¬ μ? 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuel Bodirsky and Žaneta Semanišinová 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.15 urn:nbn:de:0030-drops-255045 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.15 eng https://creativecommons.org/licenses/by/4.0/legalcode