---
_id: '11831'
abstract:
- lang: eng
  text: "Graph Sparsification aims at compressing large graphs into smaller ones while
    (approximately) preserving important characteristics of the input graph. In this
    work we study Vertex Sparsifiers, i.e., sparsifiers whose goal is to reduce the
    number of vertices. Given a weighted graph G=(V,E), and a terminal set K with
    |K|=k, a quality-q vertex cut sparsifier of G is a graph H with K contained in
    V_H that preserves the value of minimum cuts separating any bipartition of K,
    up to a factor of q. We show that planar graphs with all the k terminals lying
    on the same face admit quality-1 vertex cut sparsifier of size O(k^2) that are
    also planar. Our result extends to vertex flow and distance sparsifiers. It improves
    the previous best known bound of O(k^2 2^(2k)) for cut and flow sparsifiers by
    an exponential factor, and matches an Omega(k^2) lower-bound for this class of
    graphs.\r\n\r\nWe also study vertex reachability sparsifiers for directed graphs.
    Given a digraph G=(V,E) and a terminal set K, a vertex reachability sparsifier
    of G is a digraph H=(V_H,E_H), K contained in V_H that preserves all reachability
    information among terminal pairs. We introduce the notion of reachability-preserving
    minors, i.e., we require H to be a minor of G. Among others, for general planar
    digraphs, we construct reachability-preserving minors of size O(k^2 log^2 k).
    We complement our upper-bound by showing that there exists an infinite family
    of acyclic planar digraphs such that any reachability-preserving minor must have
    Omega(k^2) vertices."
alternative_title:
- LIPIcs
article_number: '44'
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 MH, Peng P. Improved guarantees for vertex sparsification
    in planar graphs. 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.44">10.4230/LIPICS.ESA.2017.44</a>'
  apa: 'Goranci, G., Henzinger, M. H., &#38; Peng, P. (2017). Improved guarantees
    for vertex sparsification in planar graphs. 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.44">https://doi.org/10.4230/LIPICS.ESA.2017.44</a>'
  chicago: Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “Improved Guarantees
    for Vertex Sparsification in Planar Graphs.” 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.44">https://doi.org/10.4230/LIPICS.ESA.2017.44</a>.
  ieee: G. Goranci, M. H. Henzinger, and P. Peng, “Improved guarantees for vertex
    sparsification in planar graphs,” in <i>25th Annual European Symposium on Algorithms</i>,
    Vienna, Austria, 2017, vol. 87.
  ista: 'Goranci G, Henzinger MH, Peng P. 2017. Improved guarantees for vertex sparsification
    in planar graphs. 25th Annual European Symposium on Algorithms. ESA: Annual European
    Symposium on Algorithms, LIPIcs, vol. 87, 44.'
  mla: Goranci, Gramoz, et al. “Improved Guarantees for Vertex Sparsification in Planar
    Graphs.” <i>25th Annual European Symposium on Algorithms</i>, vol. 87, 44, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href="https://doi.org/10.4230/LIPICS.ESA.2017.44">10.4230/LIPICS.ESA.2017.44</a>.
  short: G. Goranci, M.H. 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-12T09:27:11Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2023-02-21T16:32:16Z
day: '01'
doi: 10.4230/LIPICS.ESA.2017.44
extern: '1'
external_id:
  arxiv:
  - '1702.01136'
intvolume: '        87'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPIcs.ESA.2017.44
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'
related_material:
  record:
  - id: '11894'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Improved guarantees for vertex sparsification in planar graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 87
year: '2017'
...
---
_id: '11832'
abstract:
- lang: eng
  text: "In this paper, we study the problem of opening centers to cluster a set of
    clients in a metric space so as to minimize the sum of the costs of the centers
    and of the cluster radii, in a dynamic environment where clients arrive and depart,
    and the solution must be updated efficiently while remaining competitive with
    respect to the current optimal solution. We call this dynamic sum-of-radii clustering
    problem.\r\n\r\nWe present a data structure that maintains a solution whose cost
    is within a constant factor of the cost of an optimal solution in metric spaces
    with bounded doubling dimension and whose worst-case update time is logarithmic
    in the parameters of the problem."
alternative_title:
- LIPIcs
article_number: '48'
article_processing_charge: No
arxiv: 1
author:
- 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: Dariusz
  full_name: Leniowski, Dariusz
  last_name: Leniowski
- first_name: Claire
  full_name: Mathieu, Claire
  last_name: Mathieu
citation:
  ama: 'Henzinger MH, Leniowski D, Mathieu C. Dynamic clustering to minimize the sum
    of radii. 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.48">10.4230/LIPICS.ESA.2017.48</a>'
  apa: 'Henzinger, M. H., Leniowski, D., &#38; Mathieu, C. (2017). Dynamic clustering
    to minimize the sum of radii. 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.48">https://doi.org/10.4230/LIPICS.ESA.2017.48</a>'
  chicago: Henzinger, Monika H, Dariusz Leniowski, and Claire Mathieu. “Dynamic Clustering
    to Minimize the Sum of Radii.” 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.48">https://doi.org/10.4230/LIPICS.ESA.2017.48</a>.
  ieee: M. H. Henzinger, D. Leniowski, and C. Mathieu, “Dynamic clustering to minimize
    the sum of radii,” in <i>25th Annual European Symposium on Algorithms</i>, Vienna,
    Austria, 2017, vol. 87.
  ista: 'Henzinger MH, Leniowski D, Mathieu C. 2017. Dynamic clustering to minimize
    the sum of radii. 25th Annual European Symposium on Algorithms. ESA: Annual European
    Symposium on Algorithms, LIPIcs, vol. 87, 48.'
  mla: Henzinger, Monika H., et al. “Dynamic Clustering to Minimize the Sum of Radii.”
    <i>25th Annual European Symposium on Algorithms</i>, vol. 87, 48, Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2017, doi:<a href="https://doi.org/10.4230/LIPICS.ESA.2017.48">10.4230/LIPICS.ESA.2017.48</a>.
  short: M.H. Henzinger, D. Leniowski, C. Mathieu, 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-12T09:58:46Z
date_published: 2017-09-01T00:00:00Z
date_updated: 2023-02-16T11:54:12Z
day: '01'
doi: 10.4230/LIPICS.ESA.2017.48
extern: '1'
external_id:
  arxiv:
  - '1707.02577'
intvolume: '        87'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPICS.ESA.2017.48
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: Dynamic clustering to minimize the sum of radii
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 87
year: '2017'
...
---
_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 MH, 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. H., &#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 H 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. H. 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 MH, 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.H. 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: 2023-02-16T11:56:37Z
day: '01'
doi: 10.4230/LIPICS.ESA.2017.45
extern: '1'
external_id:
  arxiv:
  - '1712.06473'
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'
...