Earlier Version

Improved guarantees for vertex sparsification in planar graphs

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.

Download (ext.)

Conference Paper | Published | English

Scopus indexed
Author
Goranci, Gramoz; Henzinger, MonikaISTA ; Peng, Pan
Series Title
LIPIcs
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. We 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.
Publishing Year
Date Published
2017-09-01
Proceedings Title
25th Annual European Symposium on Algorithms
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume
87
Article Number
44
Conference
ESA: Annual European Symposium on Algorithms
Conference Location
Vienna, Austria
Conference Date
2017-09-04 – 2017-09-06
ISSN
IST-REx-ID

Cite this

Goranci G, Henzinger MH, Peng P. Improved guarantees for vertex sparsification in planar graphs. In: 25th Annual European Symposium on Algorithms. Vol 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ESA.2017.44
Goranci, G., Henzinger, M. H., & Peng, P. (2017). Improved guarantees for vertex sparsification in planar graphs. In 25th Annual European Symposium on Algorithms (Vol. 87). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ESA.2017.44
Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” In 25th Annual European Symposium on Algorithms, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ESA.2017.44.
G. Goranci, M. H. Henzinger, and P. Peng, “Improved guarantees for vertex sparsification in planar graphs,” in 25th Annual European Symposium on Algorithms, Vienna, Austria, 2017, vol. 87.
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.
Goranci, Gramoz, et al. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” 25th Annual European Symposium on Algorithms, vol. 87, 44, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ESA.2017.44.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 1702.01136

Search this title in

Google Scholar
ISBN Search