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 qualityq 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 quality1 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) lowerbound 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 reachabilitypreserving minors, i.e., we require H to be a minor of G. Among others, for general planar digraphs, we construct reachabilitypreserving minors of size O(k^2 log^2 k). We complement our upperbound by showing that there exists an infinite family of acyclic planar digraphs such that any reachabilitypreserving 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:144:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770491},
ISSN = {18688969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7833},
URN = {urn:nbn:de:0030drops78337},
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 