2026-07-22T22:18:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17698 2024-03-06T11:00:20Z ddc:004 open_access

Maintaining CMSO₂ Properties on Dynamic Structures with Bounded Feedback Vertex Number Majewski, Konrad Pilipczuk, Michał Sokołowski, Marek feedback vertex set CMSO₂ formula data structure dynamic graphs fixed-parameter tractability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Konrad Majewski and Michał Pilipczuk and Marek Sokołowski 2023 Is Part Of LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2023.46 urn:nbn:de:0030-drops-176981 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.46 eng https://creativecommons.org/licenses/by/4.0/legalcode