LIPIcs.STACS.2023.46.pdf
- Filesize: 0.97 MB
- 13 pages
Document
Maintaining CMSO₂ Properties on Dynamic Structures with Bounded Feedback Vertex Number
Authors
Konrad Majewski 
,
Michał Pilipczuk ,
Marek Sokołowski
-
Part of:
Volume:
40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-03-03
File
Document Identifiers
Author Details
Cite AsGet BibTex
Konrad Majewski, Michał Pilipczuk, and Marek Sokołowski. Maintaining CMSO₂ Properties on Dynamic Structures with Bounded Feedback Vertex Number. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.STACS.2023.46
https://doi.org/10.4230/LIPIcs.STACS.2023.46
Abstract
Let 𝜑 be a sentence of CMSO₂ (monadic second-order logic with quantification over edge subsets and counting modular predicates) over the signature of graphs. We present a dynamic data structure that for a given graph G that is updated by edge insertions and edge deletions, maintains whether 𝜑 is satisfied in G. The data structure is required to correctly report the outcome only when the feedback vertex number of G does not exceed a fixed constant k, otherwise it reports that the feedback vertex number is too large. With this assumption, we guarantee amortized update time O_{𝜑,k}(log n).
By combining this result with a classic theorem of Erdős and Pósa, we give a fully dynamic data structure that maintains whether a graph contains a packing of k vertex-disjoint cycles with amortized update time O_k(log n). Our data structure also works in a larger generality of relational structures over binary signatures.
Subject Classification
ACM Subject Classification
- Theory of computation → Dynamic graph algorithms
- Mathematics of computing → Graph algorithms
Keywords
- feedback vertex set
- CMSO₂ formula
- data structure
- dynamic graphs
- fixed-parameter tractability
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Josh Alman, Matthias Mnich, and Virginia Vassilevska Williams. Dynamic Parameterized Problems and Algorithms. ACM Trans. Algorithms, 16(4):45:1-45:46, 2020. URL: https://doi.org/10.1145/3395037.
- Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Maintaining information in fully dynamic trees with top trees. ACM Trans. Algorithms, 1(2):243-264, 2005. URL: https://doi.org/10.1145/1103963.1103966.
- Jiehua Chen, Wojciech Czerwinski, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Marcin Pilipczuk, Michał Pilipczuk, Manuel Sorge, Bartlomiej Wróblewski, and Anna Zych-Pawlewicz. Efficient fully dynamic elimination forests with applications to detecting long paths and cycles. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pages 796-809. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.50.
- Bruno Courcelle. The Monadic Second-Order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. URL: https://doi.org/10.1016/0890-5401(90)90043-H.
- Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
- Zdeněk Dvořák, Martin Kupec, and Vojtěch Tůma. A dynamic data structure for MSO properties in graphs with bounded tree-depth. In Proceedings of the 22^nd Annual European Symposium on Algorithms, ESA 2014, volume 8737 of Lecture Notes in Computer Science, pages 334-345. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-44777-2_28.
- Zdeněk Dvořák and Vojtěch Tůma. A dynamic data structure for counting subgraphs in sparse graphs. In Proceedings of the 13^th International Symposium on Algorithms and Data Structures, WADS 2013, volume 8037 of Lecture Notes in Computer Science, pages 304-315. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40104-6_27.
- David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Thomas H. Spencer. Separator based sparsification. I. Planary testing and minimum spanning trees. J. Comput. Syst. Sci., 52(1):3-27, 1996. URL: https://doi.org/10.1006/jcss.1996.0002.
-
Paul Erdős and Lajos Pósa. On the maximal number of disjoint circuits of a graph. Publ. Math. Debrecen, 9:3-12, 1962.
-
Martin Grohe. Logic, graphs, and algorithms. In Jörg Flum, Erich Grädel, and Thomas Wilke, editors, Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas], volume 2 of Texts in Logic and Games, pages 357-422. Amsterdam University Press, 2008.
- Yoichi Iwata and Keigo Oka. Fast dynamic graph algorithms for parameterized problems. In Proceedings of the 14^th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014, volume 8503 of Lecture Notes in Computer Science, pages 241-252. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-08404-6_21.
- Frank Kammer and Andrej Sajenko. FPT-space graph kernelizations. CoRR, abs/2007.11643, 2020. URL: http://arxiv.org/abs/2007.11643.
- Konrad Majewski, Michal Pilipczuk, and Marek Sokolowski. Maintaining CMSO_2 properties on dynamic structures with bounded feedback vertex number. CoRR, abs/2107.06232, 2021. URL: http://arxiv.org/abs/2107.06232.
- Matthias Niewerth. MSO queries on trees: Enumerating answers under updates using forest algebras. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, pages 769-778. ACM, 2018. URL: https://doi.org/10.1145/3209108.3209144.
-
Mihai Pǎtraşcu and Erik D. Demaine. Lower bounds for dynamic connectivity. In Proceedings of the 36^th Annual ACM Symposium on Theory of Computing, STOC 2004, pages 546-553. ACM, 2004.