Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909465744244736 |
|---|---|
| author | Majewski, Konrad Pilipczuk, Michał Sokołowski, Marek |
| author_facet | Majewski, Konrad Pilipczuk, Michał Sokołowski, Marek |
| contents | Let $φ$ be a sentence of $\mathsf{CMSO}_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 ${\cal O}_{φ,k}(\log n)$. If we additionally assume that the feedback vertex number of $G$ never exceeds $k$, this update time guarantee is worst-case.
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 ${\cal O}_{k}(\log n)$. Our data structure also works in a larger generality of relational structures over binary signatures. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2107_06232 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number Majewski, Konrad Pilipczuk, Michał Sokołowski, Marek Data Structures and Algorithms Discrete Mathematics Logic in Computer Science Let $φ$ be a sentence of $\mathsf{CMSO}_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 ${\cal O}_{φ,k}(\log n)$. If we additionally assume that the feedback vertex number of $G$ never exceeds $k$, this update time guarantee is worst-case. 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 ${\cal O}_{k}(\log n)$. Our data structure also works in a larger generality of relational structures over binary signatures. |
| title | Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number |
| topic | Data Structures and Algorithms Discrete Mathematics Logic in Computer Science |
| url | https://arxiv.org/abs/2107.06232 |