---
res:
bibo_abstract:
- "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.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Gramoz
foaf_name: Goranci, Gramoz
foaf_surname: Goranci
- foaf_Person:
foaf_givenName: Monika H
foaf_name: Henzinger, Monika H
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
orcid: 0000-0002-5008-6530
- foaf_Person:
foaf_givenName: Pan
foaf_name: Peng, Pan
foaf_surname: Peng
bibo_doi: 10.4230/LIPICS.ESA.2017.44
bibo_volume: 87
dct_date: 2017^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/1868-8969
- http://id.crossref.org/issn/978-3-95977-049-1
dct_language: eng
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
dct_title: Improved guarantees for vertex sparsification in planar graphs@
...