---
_id: '11833'
abstract:
- lang: eng
  text: "We introduce a new algorithmic framework for designing dynamic graph algorithms
    in minor-free graphs, by exploiting the structure of such graphs and a tool called
    vertex sparsification, which is a way to compress large graphs into small ones
    that well preserve relevant properties among a subset of vertices and has previously
    mainly been used in the design of approximation algorithms.\r\n\r\nUsing this
    framework, we obtain a Monte Carlo randomized fully dynamic algorithm for (1 +
    epsilon)-approximating the energy of electrical flows in n-vertex planar graphs
    with tilde{O}(r epsilon^{-2}) worst-case update time and tilde{O}((r + n / sqrt{r})
    epsilon^{-2}) worst-case query time, for any r larger than some constant. For
    r=n^{2/3}, this gives tilde{O}(n^{2/3} epsilon^{-2}) update time and tilde{O}(n^{2/3}
    epsilon^{-2}) query time. We also extend this algorithm to work for minor-free
    graphs with similar approximation and running time guarantees. Furthermore, we
    illustrate our framework on the all-pairs max flow and shortest path problems
    by giving corresponding dynamic algorithms in minor-free graphs with both sublinear
    update and query times. To the best of our knowledge, our results are the first
    to systematically establish such a connection between dynamic graph algorithms
    and vertex sparsification.\r\n\r\nWe also present both upper bound and lower bound
    for maintaining the energy of electrical flows in the incremental subgraph model,
    where updates consist of only vertex activations, which might be of independent
    interest."
alternative_title:
- LIPIcs
article_number: '45'
article_processing_charge: No
arxiv: 1
author:
- first_name: Gramoz
  full_name: Goranci, Gramoz
  last_name: Goranci
- 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: Pan
  full_name: Peng, Pan
  last_name: Peng
citation:
  ama: 'Goranci G, Henzinger M, Peng P. The power of vertex sparsifiers in dynamic
    graph algorithms. In: <i>25th Annual European Symposium on Algorithms</i>. Vol
    87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href="https://doi.org/10.4230/LIPICS.ESA.2017.45">10.4230/LIPICS.ESA.2017.45</a>'
  apa: 'Goranci, G., Henzinger, M., &#38; Peng, P. (2017). The power of vertex sparsifiers
    in dynamic graph algorithms. In <i>25th Annual European Symposium on Algorithms</i>
    (Vol. 87). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPICS.ESA.2017.45">https://doi.org/10.4230/LIPICS.ESA.2017.45</a>'
  chicago: Goranci, Gramoz, Monika Henzinger, and Pan Peng. “The Power of Vertex Sparsifiers
    in Dynamic Graph Algorithms.” In <i>25th Annual European Symposium on Algorithms</i>,
    Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href="https://doi.org/10.4230/LIPICS.ESA.2017.45">https://doi.org/10.4230/LIPICS.ESA.2017.45</a>.
  ieee: G. Goranci, M. Henzinger, and P. Peng, “The power of vertex sparsifiers in
    dynamic graph algorithms,” in <i>25th Annual European Symposium on Algorithms</i>,
    Vienna, Austria, 2017, vol. 87.
  ista: 'Goranci G, Henzinger M, Peng P. 2017. The power of vertex sparsifiers in
    dynamic graph algorithms. 25th Annual European Symposium on Algorithms. ESA: Annual
    European Symposium on Algorithms, LIPIcs, vol. 87, 45.'
  mla: Goranci, Gramoz, et al. “The Power of Vertex Sparsifiers in Dynamic Graph Algorithms.”
    <i>25th Annual European Symposium on Algorithms</i>, vol. 87, 45, Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2017, doi:<a href="https://doi.org/10.4230/LIPICS.ESA.2017.45">10.4230/LIPICS.ESA.2017.45</a>.
  short: G. Goranci, M. Henzinger, P. Peng, in:, 25th Annual European Symposium on
    Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
conference:
  end_date: 2017-09-06
  location: Vienna, Austria
  name: 'ESA: Annual European Symposium on Algorithms'
  start_date: 2017-09-04
date_created: 2022-08-12T10:46:26Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2024-11-06T11:58:29Z
day: '01'
doi: 10.4230/LIPICS.ESA.2017.45
extern: '1'
external_id:
  arxiv:
  - '1712.06473'
fulldoi: https://doi.org/10.4230/LIPICS.ESA.2017.45
intvolume: '        87'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPIcs.ESA.2017.45
month: '09'
oa: 1
oa_version: Published Version
publication: 25th Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - 978-3-95977-049-1
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: The power of vertex sparsifiers in dynamic graph algorithms
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 87
year: '2017'
...