---
_id: '11808'
abstract:
- lang: eng
  text: In recent years, significant advances have been made in the design and analysis
    of fully dynamic algorithms. However, these theoretical results have received
    very little attention from the practical perspective. Few of the algorithms are
    implemented and tested on real datasets, and their practical potential is far
    from understood. Here, we present a quick reference guide to recent engineering
    and theory results in the area of fully dynamic graph algorithms.
alternative_title:
- LIPIcs
article_number: '1'
article_processing_charge: No
arxiv: 1
author:
- first_name: Kathrin
  full_name: Hanauer, Kathrin
  last_name: Hanauer
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Christian
  full_name: Schulz, Christian
  last_name: Schulz
citation:
  ama: 'Hanauer K, Henzinger MH, Schulz C. Recent advances in fully dynamic graph
    algorithms. In: <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>.
    Vol 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:<a href="https://doi.org/10.4230/LIPIcs.SAND.2022.1">10.4230/LIPIcs.SAND.2022.1</a>'
  apa: 'Hanauer, K., Henzinger, M. H., &#38; Schulz, C. (2022). Recent advances in
    fully dynamic graph algorithms. In <i>1st Symposium on Algorithmic Foundations
    of Dynamic Networks</i> (Vol. 221). Virtual: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.4230/LIPIcs.SAND.2022.1">https://doi.org/10.4230/LIPIcs.SAND.2022.1</a>'
  chicago: Hanauer, Kathrin, Monika H Henzinger, and Christian Schulz. “Recent Advances
    in Fully Dynamic Graph Algorithms.” In <i>1st Symposium on Algorithmic Foundations
    of Dynamic Networks</i>, Vol. 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2022. <a href="https://doi.org/10.4230/LIPIcs.SAND.2022.1">https://doi.org/10.4230/LIPIcs.SAND.2022.1</a>.
  ieee: K. Hanauer, M. H. Henzinger, and C. Schulz, “Recent advances in fully dynamic
    graph algorithms,” in <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>,
    Virtual, 2022, vol. 221.
  ista: 'Hanauer K, Henzinger MH, Schulz C. 2022. Recent advances in fully dynamic
    graph algorithms. 1st Symposium on Algorithmic Foundations of Dynamic Networks.
    SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 221,
    1.'
  mla: Hanauer, Kathrin, et al. “Recent Advances in Fully Dynamic Graph Algorithms.”
    <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>, vol. 221,
    1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href="https://doi.org/10.4230/LIPIcs.SAND.2022.1">10.4230/LIPIcs.SAND.2022.1</a>.
  short: K. Hanauer, M.H. Henzinger, C. Schulz, in:, 1st Symposium on Algorithmic
    Foundations of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2022.
conference:
  end_date: 2022-03-30
  location: Virtual
  name: 'SAND: Symposium on Algorithmic Foundations of Dynamic Networks'
  start_date: 2022-03-28
date_created: 2022-08-11T14:35:52Z
date_published: 2022-04-29T00:00:00Z
date_updated: 2023-02-14T08:14:41Z
day: '29'
doi: 10.4230/LIPIcs.SAND.2022.1
extern: '1'
external_id:
  arxiv:
  - '2102.11169'
intvolume: '       221'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPIcs.SAND.2022.1
month: '04'
oa: 1
oa_version: Published Version
publication: 1st Symposium on Algorithmic Foundations of Dynamic Networks
publication_identifier:
  eissn:
  - 1868-8969
  isbn:
  - '9783959772242'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Recent advances in fully dynamic graph algorithms
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 221
year: '2022'
...
---
_id: '11812'
abstract:
- lang: eng
  text: "This paper presents a comprehensive study of algorithms for maintaining the
    number of all connected four-vertex subgraphs in a dynamic graph. Specifically,
    our algorithms maintain the number of paths of length three in deterministic amortized
    O(m^{1/2}) update time, and any other connected four-vertex subgraph which is
    not a clique in deterministic amortized update time O(m^{2/3}). Queries can be
    answered in constant time. We also study the query times for subgraphs containing
    an arbitrary edge that is supplied only with the query as well as the case where
    only subgraphs containing a vertex s that is fixed beforehand are considered.
    For length-3 paths, paws, 4-cycles, and diamonds our bounds match or are not far
    from (conditional) lower bounds: Based on the OMv conjecture we show that any
    dynamic algorithm that detects the existence of paws, diamonds, or 4-cycles or
    that counts length-3 paths takes update time Ω(m^{1/2-δ}).\r\nAdditionally, for
    4-cliques and all connected induced subgraphs, we show a lower bound of Ω(m^{1-δ})
    for any small constant δ > 0 for the amortized update time, assuming the static
    combinatorial 4-clique conjecture holds. This shows that the O(m) algorithm by
    Eppstein et al. [David Eppstein et al., 2012] for these subgraphs cannot be improved
    by a polynomial factor."
alternative_title:
- LIPIcs
article_number: '18'
article_processing_charge: No
arxiv: 1
author:
- first_name: Kathrin
  full_name: Hanauer, Kathrin
  last_name: Hanauer
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Qi Cheng
  full_name: Hua, Qi Cheng
  last_name: Hua
citation:
  ama: 'Hanauer K, Henzinger MH, Hua QC. Fully dynamic four-vertex subgraph counting.
    In: <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>. Vol 221.
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:<a href="https://doi.org/10.4230/LIPIcs.SAND.2022.18">10.4230/LIPIcs.SAND.2022.18</a>'
  apa: 'Hanauer, K., Henzinger, M. H., &#38; Hua, Q. C. (2022). Fully dynamic four-vertex
    subgraph counting. In <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>
    (Vol. 221). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.SAND.2022.18">https://doi.org/10.4230/LIPIcs.SAND.2022.18</a>'
  chicago: Hanauer, Kathrin, Monika H Henzinger, and Qi Cheng Hua. “Fully Dynamic
    Four-Vertex Subgraph Counting.” In <i>1st Symposium on Algorithmic Foundations
    of Dynamic Networks</i>, Vol. 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2022. <a href="https://doi.org/10.4230/LIPIcs.SAND.2022.18">https://doi.org/10.4230/LIPIcs.SAND.2022.18</a>.
  ieee: K. Hanauer, M. H. Henzinger, and Q. C. Hua, “Fully dynamic four-vertex subgraph
    counting,” in <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>,
    Virtual, 2022, vol. 221.
  ista: 'Hanauer K, Henzinger MH, Hua QC. 2022. Fully dynamic four-vertex subgraph
    counting. 1st Symposium on Algorithmic Foundations of Dynamic Networks. SAND:
    Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 221, 18.'
  mla: Hanauer, Kathrin, et al. “Fully Dynamic Four-Vertex Subgraph Counting.” <i>1st
    Symposium on Algorithmic Foundations of Dynamic Networks</i>, vol. 221, 18, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href="https://doi.org/10.4230/LIPIcs.SAND.2022.18">10.4230/LIPIcs.SAND.2022.18</a>.
  short: K. Hanauer, M.H. Henzinger, Q.C. Hua, in:, 1st Symposium on Algorithmic Foundations
    of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
conference:
  end_date: 2022-04-30
  location: Virtual
  name: 'SAND: Symposium on Algorithmic Foundations of Dynamic Networks'
  start_date: 2022-04-28
date_created: 2022-08-12T06:57:55Z
date_published: 2022-04-29T00:00:00Z
date_updated: 2023-02-14T08:25:42Z
day: '29'
doi: 10.4230/LIPIcs.SAND.2022.18
extern: '1'
external_id:
  arxiv:
  - '2106.15524'
intvolume: '       221'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPIcs.SAND.2022.18
month: '04'
oa: 1
oa_version: Published Version
publication: 1st Symposium on Algorithmic Foundations of Dynamic Networks
publication_identifier:
  isbn:
  - '9783959772242'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fully dynamic four-vertex subgraph counting
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 221
year: '2022'
...