[{"das_tickbox":"1","doi":"10.1016/j.ipl.2026.106663","year":"2026","day":"30","acknowledgement":"This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 101034413 and from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (MoDynStruct, No. 101019564) Image 1 dummy alt text. Zofia Stefankovic was partially supported by the ISTernship program of the Institute of Science and Technology Austria and OEAD.","OA_type":"closed access","keyword":["Dynamic algorithms","Graph algorithms","Directed graphs","Lower bounds","Upper bounds"],"fulldoi":"https://doi.org/10.1016/j.ipl.2026.106663","abstract":[{"lang":"eng","text":"Efficient data structures for computing the cutset of a set of nodes in a graph undergoing dynamic edge insertions/deletions are well-studied in undirected graphs. We study this problem in directed graphs and show a reduction from the Online Boolean Matrix-Vector Multiplication Conjecture (OMv) introduced by Henzinger et al. [STOC’15]. We prove conditional on OMv that a dynamic data structure computing the directed cutset of a set of nodes cannot have an amortized time of both O(n2−ε) for a query operation and O(n1−ε) for an update operation, for any constant ε > 0, even when an adversary’s operations are restricted to the incremental or decremental settings. We further give algorithms to match these lower bounds."}],"ec_funded":1,"project":[{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413","call_identifier":"H2020"},{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","name":"The design and evaluation of modern fully dynamic data structures","grant_number":"101019564","call_identifier":"H2020"}],"volume":195,"publisher":"Elsevier","supplementarymaterial":"no","publication":"Information Processing Letters","department":[{"_id":"MoHe"}],"publication_identifier":{"issn":["0020-0190"]},"_id":"22812","article_number":"106663","intvolume":"       195","scopus_import":"1","title":"Tight bounds on the performance of dynamic directed cutset data structures based on OMv","researchdata_availability":"no","article_type":"original","date_published":"2026-08-30T00:00:00Z","status":"public","language":[{"iso":"eng"}],"date_updated":"2026-09-09T11:55:47Z","date_created":"2026-09-06T22:01:55Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","month":"08","citation":{"ista":"Hahn N, Henzinger M, Stefankovic Z. 2026. Tight bounds on the performance of dynamic directed cutset data structures based on OMv. Information Processing Letters. 195, 106663.","short":"N. Hahn, M. Henzinger, Z. Stefankovic, Information Processing Letters 195 (2026).","mla":"Hahn, Niklas, et al. “Tight Bounds on the Performance of Dynamic Directed Cutset Data Structures Based on OMv.” <i>Information Processing Letters</i>, vol. 195, 106663, Elsevier, 2026, doi:<a href=\"https://doi.org/10.1016/j.ipl.2026.106663\">10.1016/j.ipl.2026.106663</a>.","chicago":"Hahn, Niklas, Monika Henzinger, and Zofia Stefankovic. “Tight Bounds on the Performance of Dynamic Directed Cutset Data Structures Based on OMv.” <i>Information Processing Letters</i>. Elsevier, 2026. <a href=\"https://doi.org/10.1016/j.ipl.2026.106663\">https://doi.org/10.1016/j.ipl.2026.106663</a>.","ieee":"N. Hahn, M. Henzinger, and Z. Stefankovic, “Tight bounds on the performance of dynamic directed cutset data structures based on OMv,” <i>Information Processing Letters</i>, vol. 195. Elsevier, 2026.","apa":"Hahn, N., Henzinger, M., &#38; Stefankovic, Z. (2026). Tight bounds on the performance of dynamic directed cutset data structures based on OMv. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ipl.2026.106663\">https://doi.org/10.1016/j.ipl.2026.106663</a>","ama":"Hahn N, Henzinger M, Stefankovic Z. Tight bounds on the performance of dynamic directed cutset data structures based on OMv. <i>Information Processing Letters</i>. 2026;195. doi:<a href=\"https://doi.org/10.1016/j.ipl.2026.106663\">10.1016/j.ipl.2026.106663</a>"},"oa_version":"None","type":"journal_article","dataavailabilitystatement":"No data was used for the research described in the article.","author":[{"first_name":"Niklas","full_name":"Hahn, Niklas","id":"0a01c7b2-b823-11ed-9928-cc3f874f9ffd","last_name":"Hahn"},{"orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H"},{"full_name":"Stefankovic, Zofia","first_name":"Zofia","last_name":"Stefankovic"}],"publication_status":"epub_ahead","quality_controlled":"1"},{"researchdata_availability":"no","title":"DAG covers for structured graphs: The Steiner point effect","scopus_import":"1","article_number":"94:1-94:18","intvolume":"       388","date_published":"2026-08-25T00:00:00Z","corr_author":"1","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959774451"]},"oa":1,"department":[{"_id":"MoHe"}],"_id":"22918","external_id":{"arxiv":["2604.04186"]},"publication":"34th Annual European Symposium on Algorithms","supplementarymaterial":"yes","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","arxiv":1,"keyword":["Directed graphs","DAG (directed acyclic graphs)","distortion","metric embeddings","planar graph","treewidth"],"fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2026.94","acknowledgement":"This work was initiated at Dagstuhl Seminar 25212: Metric Sketching and\r\nDynamic Algorithms for Geometric and Topological Graphs. We thank the organizers and other\r\nparticipants for a productive environment.\r\nujoy Bhore: Work supported in part by ANRF ARG-MATRICS, Grant 002465.\r\nHsien-Chih Chang: Supported by the U.S. National Science Foundation Grant No. CCF-2443017.\r\nJonathan Conroy: Supported by the U.S. National Science Foundation Grant No. CCF-2443017.\r\nArnold Filtser: This research was supported by the ISRAEL SCIENCE FOUNDATION (grant No.\r\n1042/22).\r\nEunjin Oh: Supported by Institute of Information & Communications Technology Planning &\r\nEvaluation (IITP) grant funded by the Korea government (MSIT) (No. RS-2024-00440239, Sublinear\r\nScalable Algorithms for Large-Scale Data Analysis) and the National Research Foundation of Korea\r\n(NRF) grant funded by the Korea government (MSIT) (No. RS-2024-00358505).\r\nNicole Wein: Supported by NSF CAREER award 2541910.\r\nDa Wei Zheng: This project has received funding from the Austrian Science Fund (FWF) grant\r\nDOI 10.55776/I5982. For open access purposes, the author has applied a CC BY public copyright\r\nlicense to any author-accepted manuscript version arising from this submission.","day":"25","OA_type":"gold","doi":"10.4230/LIPIcs.ESA.2026.94","year":"2026","das_tickbox":"0","volume":388,"project":[{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982"}],"abstract":[{"lang":"eng","text":"Given a weighted digraph G, a (t,g,μ)-DAG cover is a collection of g dominating DAGs D_1,… ,D_g such that all distances are approximately preserved: for every pair (u,v) of vertices, min_id_{D_i}(u,v) ≤ t⋅ d_G(u,v), and the total number of non-G edges is bounded by |(∪_i D_i)⧵ G| ≤ μ. Assadi, Hoppenworth, and Wein [STOC 25] and Filtser [SODA 26] studied DAG covers for general digraphs. This paper initiates the study of Steiner DAG cover, where the DAGs are allowed to contain Steiner points. \r\nWe obtain Steiner DAG covers on the important classes of planar digraphs and low-treewidth digraphs. Specifically, we show that any digraph with treewidth tw admits a (1,2,Õ(n⋅tw))-Steiner DAG cover. For planar digraphs we provide a (1+ε,2,Õ_ε(n))-Steiner DAG cover.\r\nWe also demonstrate a stark difference between Steiner and non-Steiner DAG covers. As a lower bound, we show that any non-Steiner DAG cover for graphs with treewidth 1 with stretch t < 2 and sub-quadratic number of extra edges requires Ω(log n) DAGs."}],"publication_status":"published","alternative_title":["LIPIcs"],"author":[{"last_name":"Bhore","first_name":"Sujoy","full_name":"Bhore, Sujoy"},{"last_name":"Chang","full_name":"Chang, Hsien Chih","first_name":"Hsien Chih"},{"first_name":"Jonathan","full_name":"Conroy, Jonathan","last_name":"Conroy"},{"full_name":"Filtser, Arnold","first_name":"Arnold","last_name":"Filtser"},{"last_name":"Oh","first_name":"Eunjin","full_name":"Oh, Eunjin"},{"last_name":"Wein","full_name":"Wein, Nicole","first_name":"Nicole"},{"last_name":"Zheng","id":"af77956b-e859-11ef-8dc9-d301b898e32f","full_name":"Zheng, Da Wei","first_name":"Da Wei"}],"type":"conference","file_date_updated":"2026-09-17T10:09:22Z","quality_controlled":"1","article_processing_charge":"Yes","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"location":"L’Aquila, Italy","end_date":"2026-09-04","start_date":"2026-08-31","name":"ESA: European Symposium on Algorithms"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"citation":{"mla":"Bhore, Sujoy, et al. “DAG Covers for Structured Graphs: The Steiner Point Effect.” <i>34th Annual European Symposium on Algorithms</i>, vol. 388, 94:1-94:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.94\">10.4230/LIPIcs.ESA.2026.94</a>.","ista":"Bhore S, Chang HC, Conroy J, Filtser A, Oh E, Wein N, Zheng DW. 2026. DAG covers for structured graphs: The Steiner point effect. 34th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 94:1-94:18.","short":"S. Bhore, H.C. Chang, J. Conroy, A. Filtser, E. Oh, N. Wein, D.W. Zheng, in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","ama":"Bhore S, Chang HC, Conroy J, et al. DAG covers for structured graphs: The Steiner point effect. In: <i>34th Annual European Symposium on Algorithms</i>. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.94\">10.4230/LIPIcs.ESA.2026.94</a>","apa":"Bhore, S., Chang, H. C., Conroy, J., Filtser, A., Oh, E., Wein, N., &#38; Zheng, D. W. (2026). DAG covers for structured graphs: The Steiner point effect. In <i>34th Annual European Symposium on Algorithms</i> (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.94\">https://doi.org/10.4230/LIPIcs.ESA.2026.94</a>","ieee":"S. Bhore <i>et al.</i>, “DAG covers for structured graphs: The Steiner point effect,” in <i>34th Annual European Symposium on Algorithms</i>, L’Aquila, Italy, 2026, vol. 388.","chicago":"Bhore, Sujoy, Hsien Chih Chang, Jonathan Conroy, Arnold Filtser, Eunjin Oh, Nicole Wein, and Da Wei Zheng. “DAG Covers for Structured Graphs: The Steiner Point Effect.” In <i>34th Annual European Symposium on Algorithms</i>, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.94\">https://doi.org/10.4230/LIPIcs.ESA.2026.94</a>."},"oa_version":"Published Version","month":"08","file":[{"access_level":"open_access","file_size":1123327,"file_id":"22948","content_type":"application/pdf","checksum":"2082683b3b72865c6a795305e5d61276","success":1,"creator":"dernst","file_name":"2026_LIPIcsESA_Bhore.pdf","date_updated":"2026-09-17T10:09:22Z","relation":"main_file","date_created":"2026-09-17T10:09:22Z"}],"date_created":"2026-09-13T22:01:53Z","date_updated":"2026-09-17T10:27:46Z","has_accepted_license":"1","status":"public","language":[{"iso":"eng"}],"OA_place":"publisher","ddc":["000"]}]