{"id":"arxiv/2601.05346","url":"https://arxiv.org/abs/2601.05346","tags":["math.LO","cs.CC","cs.DB"],"score":0,"title":"The Complexity of Resilience for Digraph Queries","domain":"math.LO","source":"arxiv","authors":["Manuel Bodirsky","Žaneta Semanišinová"],"reviews":0,"subject":"math.LO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-08","reactions":{}}