---
_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 M, 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., &#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 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. 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 M, 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. 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: 2024-11-06T08:22:47Z
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'
...