---
OA_type: closed access
_id: '22812'
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.
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.
article_number: '106663'
article_processing_charge: No
article_type: original
author:
- first_name: Niklas
  full_name: Hahn, Niklas
  id: 0a01c7b2-b823-11ed-9928-cc3f874f9ffd
  last_name: Hahn
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Zofia
  full_name: Stefankovic, Zofia
  last_name: Stefankovic
citation:
  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>
  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>
  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.
  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.
  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>.
  short: N. Hahn, M. Henzinger, Z. Stefankovic, Information Processing Letters 195
    (2026).
das_tickbox: '1'
dataavailabilitystatement: No data was used for the research described in the article.
date_created: 2026-09-06T22:01:55Z
date_published: 2026-08-30T00:00:00Z
date_updated: 2026-09-09T11:55:47Z
day: '30'
department:
- _id: MoHe
doi: 10.1016/j.ipl.2026.106663
ec_funded: 1
fulldoi: https://doi.org/10.1016/j.ipl.2026.106663
intvolume: '       195'
keyword:
- Dynamic algorithms
- Graph algorithms
- Directed graphs
- Lower bounds
- Upper bounds
language:
- iso: eng
month: '08'
oa_version: None
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
  call_identifier: H2020
  grant_number: '101019564'
  name: The design and evaluation of modern fully dynamic data structures
publication: Information Processing Letters
publication_identifier:
  issn:
  - 0020-0190
publication_status: epub_ahead
publisher: Elsevier
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Tight bounds on the performance of dynamic directed cutset data structures
  based on OMv
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 195
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22918'
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."
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."
alternative_title:
- LIPIcs
article_number: 94:1-94:18
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Sujoy
  full_name: Bhore, Sujoy
  last_name: Bhore
- first_name: Hsien Chih
  full_name: Chang, Hsien Chih
  last_name: Chang
- first_name: Jonathan
  full_name: Conroy, Jonathan
  last_name: Conroy
- first_name: Arnold
  full_name: Filtser, Arnold
  last_name: Filtser
- first_name: Eunjin
  full_name: Oh, Eunjin
  last_name: Oh
- first_name: Nicole
  full_name: Wein, Nicole
  last_name: Wein
- first_name: Da Wei
  full_name: Zheng, Da Wei
  id: af77956b-e859-11ef-8dc9-d301b898e32f
  last_name: Zheng
citation:
  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>'
  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>.'
  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.'
  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.'
  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>.'
  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.
conference:
  end_date: 2026-09-04
  location: L’Aquila, Italy
  name: 'ESA: European Symposium on Algorithms'
  start_date: 2026-08-31
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-13T22:01:53Z
date_published: 2026-08-25T00:00:00Z
date_updated: 2026-09-17T10:27:46Z
day: '25'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2026.94
external_id:
  arxiv:
  - '2604.04186'
file:
- access_level: open_access
  checksum: 2082683b3b72865c6a795305e5d61276
  content_type: application/pdf
  creator: dernst
  date_created: 2026-09-17T10:09:22Z
  date_updated: 2026-09-17T10:09:22Z
  file_id: '22948'
  file_name: 2026_LIPIcsESA_Bhore.pdf
  file_size: 1123327
  relation: main_file
  success: 1
file_date_updated: 2026-09-17T10:09:22Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2026.94
has_accepted_license: '1'
intvolume: '       388'
keyword:
- Directed graphs
- DAG (directed acyclic graphs)
- distortion
- metric embeddings
- planar graph
- treewidth
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
  grant_number: I05982
  name: Static and Dynamic Hierarchical Graph Decompositions
publication: 34th Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '9783959774451'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: yes
title: 'DAG covers for structured graphs: The Steiner point effect'
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 388
year: '2026'
...