Upper and lower bounds for fully retroactive graph problems
Henzinger MH, 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.
Download (ext.)
https://arxiv.org/abs/1910.03332
[Preprint]
Conference Paper
| Published
| English
Scopus indexed
Author
Henzinger, MonikaISTA ;
Wu, Xiaowei
Series Title
LNCS
Abstract
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.
In 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 π(π1βπ) time per operation, for any constant π>0. Furthermore, We provide RDS with almost tight time per operation. We give fully RDS for maintaining the maximum degree, connectivity and MSF in πΜ (π) time per operation. We also give an algorithm for the incremental (insertion-only) fully retroactive connectivity with πΜ (1) time per operation, showing that the lower bound cannot be extended to this setting.
We 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.
Publishing Year
Date Published
2021-08-09
Proceedings Title
17th International Symposium on Algorithms and Data Structures
Volume
12808
Page
471β484
Conference
WADS: Workshop on Algorithms and Data Structures
Conference Location
Virtual
Conference Date
2021-08-09 – 2021-08-11
ISBN
ISSN
eISSN
IST-REx-ID
Cite this
Henzinger MH, Wu X. Upper and lower bounds for fully retroactive graph problems. In: 17th International Symposium on Algorithms and Data Structures. Vol 12808. Springer Nature; 2021:471β484. doi:10.1007/978-3-030-83508-8_34
Henzinger, M. H., & Wu, X. (2021). Upper and lower bounds for fully retroactive graph problems. In 17th International Symposium on Algorithms and Data Structures (Vol. 12808, pp. 471β484). Virtual: Springer Nature. https://doi.org/10.1007/978-3-030-83508-8_34
Henzinger, Monika H, and Xiaowei Wu. βUpper and Lower Bounds for Fully Retroactive Graph Problems.β In 17th International Symposium on Algorithms and Data Structures, 12808:471β484. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-83508-8_34.
M. H. Henzinger and X. Wu, βUpper and lower bounds for fully retroactive graph problems,β in 17th International Symposium on Algorithms and Data Structures, Virtual, 2021, vol. 12808, pp. 471β484.
Henzinger MH, 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.
Henzinger, Monika H., and Xiaowei Wu. βUpper and Lower Bounds for Fully Retroactive Graph Problems.β 17th International Symposium on Algorithms and Data Structures, vol. 12808, Springer Nature, 2021, pp. 471β484, doi:10.1007/978-3-030-83508-8_34.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1910.03332