License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.65
URN: urn:nbn:de:0030-drops-170035
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17003/
Go to the corresponding LIPIcs Volume Portal

Henzinger, Monika ; Paz, Ami ; Sricharan, A. R.

Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs

pdf-format:
LIPIcs-ESA-2022-65.pdf (0.9 MB)

Abstract

A dynamic graph algorithm is a data structure that answers queries about a property of the current graph while supporting graph modifications such as edge insertions and deletions. Prior work has shown strong conditional lower bounds for general dynamic graphs, yet graph families that arise in practice often exhibit structural properties that the existing lower bound constructions do not possess. We study three specific graph families that are ubiquitous, namely constant-degree graphs, power-law graphs, and expander graphs, and give the first conditional lower bounds for them. Our results show that even when restricting our attention to one of these graph classes, any algorithm for fundamental graph problems such as distance computation or approximation or maximum matching, cannot simultaneously achieve a sub-polynomial update time and query time. For example, we show that the same lower bounds as for general graphs hold for maximum matching and (s,t)-distance in constant-degree graphs, power-law graphs or expanders. Namely, in an m-edge graph, there exists no dynamic algorithms with both O(m^{1/2 - ε}) update time and O(m^{1 -ε}) query time, for any small ε > 0. Note that for (s,t)-distance the trivial dynamic algorithm achieves an almost matching upper bound of constant update time and O(m) query time. We prove similar bounds for the other graph families and for other fundamental problems such as densest subgraph detection and perfect matching.

BibTeX - Entry

@InProceedings{henzinger_et_al:LIPIcs.ESA.2022.65,
  author =	{Henzinger, Monika and Paz, Ami and Sricharan, A. R.},
  title =	{{Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{65:1--65:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17003},
  URN =		{urn:nbn:de:0030-drops-170035},
  doi =		{10.4230/LIPIcs.ESA.2022.65},
  annote =	{Keywords: Dynamic graph algorithms, Expander graphs, Power-law graphs}
}

Keywords: Dynamic graph algorithms, Expander graphs, Power-law graphs
Collection: 30th Annual European Symposium on Algorithms (ESA 2022)
Issue Date: 2022
Date of publication: 01.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI