The Complexity of Resilience for Digraph Queries
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.05346
curl -X POST /api/v1/records/arxiv/2601.05346/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.05346/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'