---
_id: '11852'
abstract:
- lang: eng
  text: We present a general framework of designing efficient dynamic approximate
    algorithms for optimization problems on undirected graphs. In particular, we develop
    a technique that, given any problem that admits a certain notion of vertex sparsifiers,
    gives data structures that maintain approximate solutions in sub-linear update
    and query time. We illustrate the applicability of our paradigm to the following
    problems. (1)A fully-dynamic algorithm that approximates all-pair maximum-flows/minimum-cuts
    up to a nearly logarithmic factor in O~(n2/3) 11The O~(⋅) notation is used in
    this paper to hide poly-logarithmic factors. amortized time against an oblivious
    adversary, and O~(m3/4) time against an adaptive adversary. (2)An incremental
    data structure that maintains O(1) - approximate shortest path in no(1) time per
    operation, as well as fully dynamic approximate all-pair shortest path and transshipment
    in O~(n2/3+o(1)) amortized time per operation. (3)A fully-dynamic algorithm that
    approximates all-pair effective resistance up to an (1+ϵ) factor in O~(n2/3+o(1)ϵ−O(1))
    amortized update time per operation. The key tool behind result (1) is the dynamic
    maintenance of an algorithmic construction due to Madry [FOCS' 10], which partitions
    a graph into a collection of simpler graph structures (known as j-trees) and approximately
    captures the cut-flow and metric structure of the graph. The O(1)-approximation
    guarantee of (2) is by adapting the distance oracles by [Thorup-Zwick JACM '05].
    Result (3) is obtained by invoking the random-walk based spectral vertex sparsifier
    by [Durfee et al. STOC '19] in a hierarchical manner, while carefully keeping
    track of the recourse among levels in the hierarchy. See https://arxiv.org/pdf/2005.02368.pdf
    for the full version of this paper.
article_processing_charge: No
arxiv: 1
author:
- first_name: Li
  full_name: Chen, Li
  last_name: Chen
- 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: Richard
  full_name: Peng, Richard
  last_name: Peng
- first_name: Thatchaphol
  full_name: Saranurak, Thatchaphol
  last_name: Saranurak
citation:
  ama: 'Chen L, Goranci G, Henzinger MH, Peng R, Saranurak T. Fast dynamic cuts, distances
    and effective resistances via vertex sparsifiers. In: <i>61st Annual Symposium
    on Foundations of Computer Science</i>. Institute of Electrical and Electronics
    Engineers; 2020:1135-1146. doi:<a href="https://doi.org/10.1109/focs46700.2020.00109">10.1109/focs46700.2020.00109</a>'
  apa: 'Chen, L., Goranci, G., Henzinger, M. H., Peng, R., &#38; Saranurak, T. (2020).
    Fast dynamic cuts, distances and effective resistances via vertex sparsifiers.
    In <i>61st Annual Symposium on Foundations of Computer Science</i> (pp. 1135–1146).
    Durham, NC, United States: Institute of Electrical and Electronics Engineers.
    <a href="https://doi.org/10.1109/focs46700.2020.00109">https://doi.org/10.1109/focs46700.2020.00109</a>'
  chicago: Chen, Li, Gramoz Goranci, Monika H Henzinger, Richard Peng, and Thatchaphol
    Saranurak. “Fast Dynamic Cuts, Distances and Effective Resistances via Vertex
    Sparsifiers.” In <i>61st Annual Symposium on Foundations of Computer Science</i>,
    1135–46. Institute of Electrical and Electronics Engineers, 2020. <a href="https://doi.org/10.1109/focs46700.2020.00109">https://doi.org/10.1109/focs46700.2020.00109</a>.
  ieee: L. Chen, G. Goranci, M. H. Henzinger, R. Peng, and T. Saranurak, “Fast dynamic
    cuts, distances and effective resistances via vertex sparsifiers,” in <i>61st
    Annual Symposium on Foundations of Computer Science</i>, Durham, NC, United States,
    2020, pp. 1135–1146.
  ista: 'Chen L, Goranci G, Henzinger MH, Peng R, Saranurak T. 2020. Fast dynamic
    cuts, distances and effective resistances via vertex sparsifiers. 61st Annual
    Symposium on Foundations of Computer Science. FOCS: Annual Symposium on Foundations
    of Computer Science, 1135–1146.'
  mla: Chen, Li, et al. “Fast Dynamic Cuts, Distances and Effective Resistances via
    Vertex Sparsifiers.” <i>61st Annual Symposium on Foundations of Computer Science</i>,
    Institute of Electrical and Electronics Engineers, 2020, pp. 1135–46, doi:<a href="https://doi.org/10.1109/focs46700.2020.00109">10.1109/focs46700.2020.00109</a>.
  short: L. Chen, G. Goranci, M.H. Henzinger, R. Peng, T. Saranurak, in:, 61st Annual
    Symposium on Foundations of Computer Science, Institute of Electrical and Electronics
    Engineers, 2020, pp. 1135–1146.
conference:
  end_date: 2020-11-19
  location: Durham, NC, United States
  name: 'FOCS: Annual Symposium on Foundations of Computer Science'
  start_date: 2020-11-16
date_created: 2022-08-16T07:33:12Z
date_published: 2020-11-01T00:00:00Z
date_updated: 2023-02-17T09:47:36Z
day: '01'
doi: 10.1109/focs46700.2020.00109
extern: '1'
external_id:
  arxiv:
  - '2005.02368'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2005.02368
month: '11'
oa: 1
oa_version: Preprint
page: 1135-1146
publication: 61st Annual Symposium on Foundations of Computer Science
publication_identifier:
  eisbn:
  - 978-1-7281-9621-3
  eissn:
  - 2575-8454
  isbn:
  - 978-1-7281-9622-0
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fast dynamic cuts, distances and effective resistances via vertex sparsifiers
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2020'
...