License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2017.44
URN: urn:nbn:de:0030-drops-78337
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7833/
Goranci, Gramoz ;
Henzinger, Monika ;
Peng, Pan
Improved Guarantees for Vertex Sparsification in Planar Graphs
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.
BibTeX - Entry
@InProceedings{goranci_et_al:LIPIcs:2017:7833,
author = {Gramoz Goranci and Monika Henzinger and Pan Peng},
title = {{Improved Guarantees for Vertex Sparsification in Planar Graphs}},
booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)},
pages = {44:1--44:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-049-1},
ISSN = {1868-8969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7833},
URN = {urn:nbn:de:0030-drops-78337},
doi = {10.4230/LIPIcs.ESA.2017.44},
annote = {Keywords: Vertex Sparsification, Graph Sparsification, Planar Graphs, Metric Embedding, Reachability}
}
|
Keywords: |
|
Vertex Sparsification, Graph Sparsification, Planar Graphs, Metric Embedding, Reachability |
|
Collection: |
|
25th Annual European Symposium on Algorithms (ESA 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
01.09.2017 |
