Document Open Access Logo

Maintaining CMSO₂ Properties on Dynamic Structures with Bounded Feedback Vertex Number

Authors Konrad Majewski , Michał Pilipczuk , Marek Sokołowski

PDF
Thumbnail PDF

File

LIPIcs.STACS.2023.46.pdf
  • Filesize: 0.97 MB
  • 13 pages

Document Identifiers

Author Details

Konrad Majewski
  • Institute of Informatics, University of Warsaw, Poland
Michał Pilipczuk
  • Institute of Informatics, University of Warsaw, Poland
Marek Sokołowski
  • Institute of Informatics, University of Warsaw, Poland

Funding

This work is a part of project BOBR that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 948057).

Cite As Get 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

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)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. Paul Erdős and Lajos Pósa. On the maximal number of disjoint circuits of a graph. Publ. Math. Debrecen, 9:3-12, 1962. Google Scholar
  10. 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. Google Scholar
  11. 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.
  12. Frank Kammer and Andrej Sajenko. FPT-space graph kernelizations. CoRR, abs/2007.11643, 2020. URL: http://arxiv.org/abs/2007.11643.
  13. 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.
  14. 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.
  15. 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. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact