The Complexity of Resilience for Digraph Queries
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
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} 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 [6] 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.
Details
| Originalsprache | Englisch |
|---|---|
| Titel | 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) |
| Redakteure/-innen | Meena Mahajan, Florin Manea, Annabelle McIver, KimThang Nguyen |
| Herausgeber (Verlag) | Schloss Dagstuhl- Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing |
| Seiten | 15:1-15:20 |
| ISBN (elektronisch) | 9783959774123 |
| Publikationsstatus | Veröffentlicht - 2026 |
| Peer-Review-Status | Ja |
Publikationsreihe
| Reihe | Leibniz international proceedings in informatics : LIPIcs |
|---|---|
| Band | 364 |
| ISSN | 1868-8969 |
Externe IDs
| ORCID | /0000-0001-8228-3611/work/208071925 |
|---|---|
| Scopus | 105037320666 |
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- unions of conjunctive queries, valued constraints, pp-constructions, resilience, computational complexity