Maintaining ๐–ข๐–ฌ๐–ฒ๐–ฎ_2 properties on dynamic structures with bounded feedback vertex number

07/13/2021
โˆ™
by   Konrad Majewski, et al.
โˆ™
0
โˆ™

Let ฯ† be a sentence of ๐–ข๐–ฌ๐–ฒ๐–ฎ_2 (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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset