---
_id: '11771'
abstract:
- lang: eng
  text: "Classic dynamic data structure problems maintain a data structure subject
    to a sequence S of updates and they answer queries using the latest version of
    the data structure, i.e., the data structure after processing the whole sequence.
    To handle operations that change the sequence S of updates, Demaine et al. [7]
    introduced retroactive data structures (RDS). A retroactive operation modifies
    the update sequence S in a given position t, called time, and either creates or
    cancels an update in S at time t. A fully retroactive data structure supports
    queries at any time t: a query at time t is answered using only the updates of
    S up to time t. While efficient RDS have been proposed for classic data structures,
    e.g., stack, priority queue and binary search tree, the retroactive version of
    graph problems are rarely studied.\r\n\r\nIn this paper we study retroactive graph
    problems including connectivity, minimum spanning forest (MSF), maximum degree,
    etc. We show that under the OMv conjecture (proposed by Henzinger et al. [15]),
    there does not exist fully RDS maintaining connectivity or MSF, or incremental
    fully RDS maintaining the maximum degree with \U0001D442(\U0001D45B1−\U0001D716)
    time per operation, for any constant \U0001D716>0. Furthermore, We provide RDS
    with almost tight time per operation. We give fully RDS for maintaining the maximum
    degree, connectivity and MSF in \U0001D442̃ (\U0001D45B) time per operation. We
    also give an algorithm for the incremental (insertion-only) fully retroactive
    connectivity with \U0001D442̃ (1) time per operation, showing that the lower bound
    cannot be extended to this setting.\r\n\r\nWe also study a restricted version
    of RDS, where the only change to S is the swap of neighboring updates and show
    that for this problem we can beat the above hardness result. This also implies
    the first non-trivial dynamic Reeb graph computation algorithm."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- 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: Xiaowei
  full_name: Wu, Xiaowei
  last_name: Wu
citation:
  ama: 'Henzinger M, Wu X. Upper and lower bounds for fully retroactive graph problems.
    In: <i>17th International Symposium on Algorithms and Data Structures</i>. Vol
    12808. Springer Nature; 2021:471–484. doi:<a href="https://doi.org/10.1007/978-3-030-83508-8_34">10.1007/978-3-030-83508-8_34</a>'
  apa: 'Henzinger, M., &#38; Wu, X. (2021). Upper and lower bounds for fully retroactive
    graph problems. In <i>17th International Symposium on Algorithms and Data Structures</i>
    (Vol. 12808, pp. 471–484). Virtual: Springer Nature. <a href="https://doi.org/10.1007/978-3-030-83508-8_34">https://doi.org/10.1007/978-3-030-83508-8_34</a>'
  chicago: Henzinger, Monika, and Xiaowei Wu. “Upper and Lower Bounds for Fully Retroactive
    Graph Problems.” In <i>17th International Symposium on Algorithms and Data Structures</i>,
    12808:471–484. Springer Nature, 2021. <a href="https://doi.org/10.1007/978-3-030-83508-8_34">https://doi.org/10.1007/978-3-030-83508-8_34</a>.
  ieee: M. Henzinger and X. Wu, “Upper and lower bounds for fully retroactive graph
    problems,” in <i>17th International Symposium on Algorithms and Data Structures</i>,
    Virtual, 2021, vol. 12808, pp. 471–484.
  ista: 'Henzinger M, Wu X. 2021. Upper and lower bounds for fully retroactive graph
    problems. 17th International Symposium on Algorithms and Data Structures. WADS:
    Workshop on Algorithms and Data Structures, LNCS, vol. 12808, 471–484.'
  mla: Henzinger, Monika, and Xiaowei Wu. “Upper and Lower Bounds for Fully Retroactive
    Graph Problems.” <i>17th International Symposium on Algorithms and Data Structures</i>,
    vol. 12808, Springer Nature, 2021, pp. 471–484, doi:<a href="https://doi.org/10.1007/978-3-030-83508-8_34">10.1007/978-3-030-83508-8_34</a>.
  short: M. Henzinger, X. Wu, in:, 17th International Symposium on Algorithms and
    Data Structures, Springer Nature, 2021, pp. 471–484.
conference:
  end_date: 2021-08-11
  location: Virtual
  name: 'WADS: Workshop on Algorithms and Data Structures'
  start_date: 2021-08-09
date_created: 2022-08-08T13:01:29Z
date_published: 2021-08-09T00:00:00Z
date_updated: 2024-11-06T12:10:14Z
day: '09'
doi: 10.1007/978-3-030-83508-8_34
extern: '1'
external_id:
  arxiv:
  - '1910.03332'
intvolume: '     12808'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1910.03332
month: '08'
oa: 1
oa_version: Preprint
page: 471–484
publication: 17th International Symposium on Algorithms and Data Structures
publication_identifier:
  eisbn:
  - '9783030835088'
  eissn:
  - 1611-3349
  isbn:
  - '9783030835071'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Upper and lower bounds for fully retroactive graph problems
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12808
year: '2021'
...