Resilience for Regular Path Queries: Towards a Complexity Classification

The resilience problem for a query and an input set or bag database is to compute the minimum number of facts to remove from the database to make the query false. In this paper, we study how to compute the resilience of Regular Path Queries (RPQs) over graph databases. Our goal is to characterize the regular languages L for which it is tractable to compute the resilience of the existentially-quantified RPQ built from L . We show that computing the resilience in this sense is tractable (even in combined complexity) for all RPQs defined from so-called local languages . By contrast, we show hardness in data complexity for RPQs defined from the following language classes (after reducing the languages to eliminate redundant words): all finite languages featuring a word containing a repeated letter, and all languages featuring a specific kind of counterexample to being local (which we call four-legged languages). The latter include in particular all languages that are not star-free . Our results also imply a dichotomy on all languages with a so-called neutral letter . We last show tractability for some classes of non-local languages, namely the so-called bipartite chain languages and one-dangling languages , and highlight some remaining obstacles towards a full dichotomy.

Authors

Institutions

Publication Details

Journal
ACM Transactions on Database Systems
Published
2026-11-13
DOI
https://doi.org/10.1145/3862467
Primary Topic
Advanced Graph Theory Research
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Resilience for Regular Path Queries: Towards a Complexity Classification

Antoine Amarilli, Neha Makhija, Martín Muñoz, Wolfgang Gatterbauer et al.
2 links
ACM Transactions on Database Systems
Advanced Graph Theory Research
article

Resilience for Regular Path Queries: Towards a Complexity Classification

Antoine Amarilli, Neha Makhija, Martín Muñoz, Wolfgang Gatterbauer, Mikaël Monet
article en

Abstract

The resilience problem for a query and an input set or bag database is to compute the minimum number of facts to remove from the database to make the query false. In this paper, we study how to compute the resilience of Regular Path Queries (RPQs) over graph databases. Our goal is to characterize the regular languages L for which it is tractable to compute the resilience of the existentially-quantified RPQ built from L . We show that computing the resilience in this sense is tractable (even in combined complexity) for all RPQs defined from so-called local languages . By contrast, we show hardness in data complexity for RPQs defined from the following language classes (after reducing the languages to eliminate redundant words): all finite languages featuring a word containing a repeated letter, and all languages featuring a specific kind of counterexample to being local (which we call four-legged languages). The latter include in particular all languages that are not star-free . Our results also imply a dichotomy on all languages with a so-called neutral letter . We last show tractability for some classes of non-local languages, namely the so-called bipartite chain languages and one-dangling languages , and highlight some remaining obstacles towards a full dichotomy.

ACM Transactions on Database Systems
Northeastern University (US), Centre Inria de l'Université de Lille (FR), Centre de Recherche en Informatique de Lens (FR)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon