{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T02:53:31Z","timestamp":1775184811538,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/501100006374","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-19-CE48-0019,ANR-18-CE23-0003-02"],"award-info":[{"award-number":["ANR-19-CE48-0019,ANR-18-CE23-0003-02"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["431183758"],"award-info":[{"award-number":["431183758"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"NSF","doi-asserted-by":"publisher","award":["IIS-1762268"],"award-info":[{"award-number":["IIS-1762268"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,9]]},"abstract":"<jats:p>\n            The\n            <jats:italic toggle=\"yes\">resilience problem<\/jats:italic>\n            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\n            <jats:italic toggle=\"yes\">L<\/jats:italic>\n            for which it is tractable to compute the resilience of the existentially-quantified RPQ built from\n            <jats:italic toggle=\"yes\">L<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            We show that computing the resilience in this sense is tractable (even in combined complexity) for all RPQs defined from so-called\n            <jats:italic toggle=\"yes\">local languages<\/jats:italic>\n            . 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\n            <jats:italic toggle=\"yes\">four-legged<\/jats:italic>\n            languages). The latter include in particular all languages that are not\n            <jats:italic toggle=\"yes\">star-free<\/jats:italic>\n            . Our results also imply hardness for all non-local languages with a so-called\n            <jats:italic toggle=\"yes\">neutral letter<\/jats:italic>\n            . We last highlight some remaining obstacles towards a full dichotomy.\n          <\/jats:p>","DOI":"10.1145\/3725245","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T15:20:31Z","timestamp":1749482431000},"page":"1-18","source":"Crossref","is-referenced-by-count":1,"title":["Resilience for Regular Path Queries: Towards a Complexity Classification"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7977-4441","authenticated-orcid":false,"given":"Antoine","family":"Amarilli","sequence":"first","affiliation":[{"name":"Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRIStAL, F-59000 Lille, France and LTCI, T\u00e9l\u00e9com Paris, Institut polytechnique de Paris, 91120 Palaiseau, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9614-0504","authenticated-orcid":false,"given":"Wolfgang","family":"Gatterbauer","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0221-6836","authenticated-orcid":false,"given":"Neha","family":"Makhija","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6158-4607","authenticated-orcid":false,"given":"Mika\u00ebl","family":"Monet","sequence":"additional","affiliation":[{"name":"Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRIStAL, F-59000 Lille, France"}]}],"member":"320","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377--2217(96)00269-X"},{"key":"e_1_2_1_2_1","volume-title":"hrefhttps:\/\/arxiv.org\/pdf\/2412.09411Resilience for regular path queries: Towards a complexity classification. arXiv preprint arXiv:2412.09411","author":"Amarilli Antoine","year":"2024","unstructured":"Antoine Amarilli, Wolfgang Gatterbauer, Neha Makhija, and Mika\u00ebl Monet. hrefhttps:\/\/arxiv.org\/pdf\/2412.09411Resilience for regular path queries: Towards a complexity classification. arXiv preprint arXiv:2412.09411, 2024."},{"key":"e_1_2_1_3_1","volume-title":"Code repository for gadget verification","author":"Amarilli Antoine","year":"2024","unstructured":"Antoine Amarilli, Wolfgang Gatterbauer, Neha Makhija, and Mika\u00ebl Monet. Code repository for gadget verification, 2024. https:\/\/osf.io\/6kfj3\/?view_only=b894b3ce8f0540f39233d761087ed92d."},{"key":"e_1_2_1_4_1","volume-title":"hrefhttps:\/\/arxiv.org\/abs\/2309.13287 Approximating queries on probabilistic graphs","author":"Amarilli Antoine","year":"2024","unstructured":"Antoine Amarilli, Timothy van Bremen, Octave Gaspard, and Kuldeep S. Meel. hrefhttps:\/\/arxiv.org\/abs\/2309.13287 Approximating queries on probabilistic graphs, 2024. href https:\/\/arxiv.org\/abs\/2309.13287 patharXiv:2309.13287."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1868237.1868241"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.104"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.07.004"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3661814.3662071"},{"key":"e_1_2_1_9_1","volume-title":"PODS","author":"Buneman Peter","year":"2002","unstructured":"Peter Buneman, Sanjeev Khanna, and Wang-Chiew Tan. hrefhttps:\/\/homepages.inf.ed.ac.uk\/opb\/papers\/PODS2002.pdfOn propagation of deletions and annotations through views. In PODS, 2002."},{"key":"e_1_2_1_10_1","volume-title":"Introduction to algorithms","author":"Cormen Thomas H.","year":"2009","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT Press, Cambridge, Mass., 3rd ed edition, 2009. URL: https:\/\/dl.acm.org\/doi\/book\/10.5555\/1614191.","edition":"3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","unstructured":"Lester Randolph Ford and Delbert R Fulkerson. hrefhttps:\/\/web.archive.org\/web\/20170809102956id_\/http:\/\/bioinfo.ict.ac.cn\/ dbu\/AlgorithmCourses\/Lectures\/FordFulkerson1956.pdfMaximal flow through a network. Canadian journal of Mathematics 8:399--404 1956. href https:\/\/doi.org\/10.4153\/cjm-1956-045--5 pathdoi:10.4153\/cjm-1956-045--5.","DOI":"10.4153\/cjm-1956-045--5"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850592"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387647"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/3--540--58201-0_92"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--540--24627--5_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.111"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2021.100642"},{"key":"e_1_2_1_18_1","unstructured":"M.Monet (https:\/\/cstheory.stackexchange.com\/users\/38111\/m monet). Is this variant of min-cut ptime? Theoretical Computer Science Stack Exchange. URL:https:\/\/cstheory.stackexchange.com\/q\/54790 (version: 2024--10--29). URL: https:\/\/cstheory.stackexchange.com\/q\/54790 href https:\/\/arxiv.org\/abs\/https:\/\/cstheory.stackexchange.com\/q\/54790 patharXiv:https:\/\/cstheory.stackexchange.com\/q\/54790."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120306"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--1--4684--2001--2_9"},{"key":"e_1_2_1_21_1","volume-title":"hrefhttps:\/\/vldb.org\/archives\/website\/2014\/program\/http:\/\/www.vldb.org\/pvldb\/vol6\/p1558-kimelfeld.pdfMulti-tuple deletion propagation: Approximations and complexity. PVLDB, 6(13)","author":"Kimelfeld Benny","year":"2013","unstructured":"Benny Kimelfeld, Jan Vondr\u00e1k, and David P Woodruff. hrefhttps:\/\/vldb.org\/archives\/website\/2014\/program\/http:\/\/www.vldb.org\/pvldb\/vol6\/p1558-kimelfeld.pdfMulti-tuple deletion propagation: Approximations and complexity. PVLDB, 6(13), 2013."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.77"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060629"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/120904202"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626715"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0927-0507(05)12007--6"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585506"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-10--1--96--115"},{"key":"e_1_2_1_29_1","volume-title":"Mathematical foundations of automata theory. https:\/\/www.irif.fr\/ jep\/PDF\/MPRI\/MPRI.pdf","author":"Pin Jean-\u00c9ric","year":"2022","unstructured":"Jean-\u00c9ric Pin. Mathematical foundations of automata theory. https:\/\/www.irif.fr\/ jep\/PDF\/MPRI\/MPRI.pdf, 2022."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139195218"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725245","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:17:50Z","timestamp":1755904670000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725245"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,9]]}},"alternative-id":["10.1145\/3725245"],"URL":"https:\/\/doi.org\/10.1145\/3725245","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,9]]}}}