Improved guarantees for vertex sparsification in planar graphs

DOI10.1137/17M1163153MaRDI QIDQ5208743zbMATH OpenWikidataFDO

Authors Gramoz Goranci, Pan Peng, Monika R. Henzinger

Publication date 10 January 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.01136

zbMATH Keywords

planar graphscut sparsifiersvertex sparsificationreachability-preserving minor

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83)

Abstract: Graph Sparsification aims at compressing large graphs into smaller ones while 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. We focus on the following notions: (1) Given a digraph $G=(V,E)$ and terminal vertices $KsubsetV$ with $|K|=k$, a (vertex) reachability sparsifier of $G$ is a digraph $H=(V_H,E_H)$, $Ksubset{V}_H$ that preserves all reachability information among terminal pairs. In this work we introduce the notion of reachability-preserving minors (RPMs) , i.e., we require $H$ to be a minor of $G$. We show any directed graph $G$ admits a RPM $H$ of size $O(k^3)$, and if $G$ is planar, then the size of $H$ improves to $O(k^{2}logk)$. We complement our upper-bound by showing that there exists an infinite family of grids such that any RPM must have $Omega(k^2)$ vertices. (2) Given a weighted undirected graph $G=(V,E)$ and terminal vertices $K$ with $|K|=k$, an exact (vertex) cut sparsifier of $G$ is a graph $H$ with $Ksubset{V}_H$ that preserves the value of minimum-cuts separating any bipartition of $K$. We show that planar graphs with all the $k$ terminals lying on the same face admit exact cut sparsifiers of size $O(k^2)$ that are also planar. Our result extends to 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.

Recommendations

• Improved guarantees for vertex sparsification in planar graphs
• Refined vertex sparsifiers of planar graphs
• An exponential lower bound for cut sparsifiers in planar graphs
• Vertex Sparsifiers: New Results from Old Techniques
• Vertex sparsifiers: new results from old techniques

Cites work

• scientific article; zbMATH DE number 1256718 (Why is no real title available?)
• scientific article; zbMATH DE number 7238981 (Why is no real title available?)
• A Hierarchy of Lower Bounds for Sublinear Additive Spanners
• A Tight Lower Bound for the Steiner Point Removal Problem on Trees
• A characterization of the components of the graphs \(D(k,q)\)
• A new series of dense graphs of high girth
• An existence theory for pairwise balanced designs. III: Proof of the existence conjectures
• An exponential lower bound for cut sparsifiers in planar graphs
• Approximate distance oracles
• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
• Characterizing multiterminal flow networks and computing flows in networks of small treewidth
• Circular planar graphs and resistor networks
• Compact oracles for reachability and approximate distances in planar digraphs
• Complexity of network synchronization
• Computing mimicking networks
• Cutting Corners Cheaply, or How to Remove Steiner Points
• Delta-Wye Transformations and the Efficient Reduction of Two-Terminal Planar Graphs
• Depth-First Search and Linear Graph Algorithms
• Distance-Preserving Graph Contractions
• Distance-preserving subgraphs of interval graphs
• Dynamic Plane Transitive Closure
• Edge-disjoint paths in planar graphs with constant congestion
• Embedding k-Outerplanar Graphs into l1
• Extensions and limits to vertex sparsification
• Flow-cut gaps for integer and fractional multiflows
• Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
• Improved guarantees for vertex sparsification in planar graphs
• Linear size distance preservers
• Metric extension operators, vertex sparsifiers and Lipschitz extendability
• Mimicking Networks and Succinct Representations of Terminal Cuts
• Multicommodity flows in planar graphs
• Near-optimal compression for the planar graph metric
• Near-optimal distance emulator for planar graphs
• On mimicking networks representing minimum terminal cuts
• On the distortion required for embedding finite metric spaces into normed spaces
• On vertex sparsifiers with Steiner nodes
• Reachability preservers: new extremal bounds and approximation algorithms
• Refined vertex sparsifiers of planar graphs
• Routing in undirected graphs with constant congestion
• Sparse Sourcewise and Pairwise Distance Preservers
• Spectral sparsification of graphs
• Steiner point removal -- distant terminals don't (really) bother
• Steiner point removal with distortion \(O(\log k)\)
• Steiner points in tree metrics don't (really) help
• The 4/3 additive spanner exponent is tight
• The Transitive Reduction of a Directed Graph
• Towards \((1 + \varepsilon)\)-approximate flow sparsifiers
• Universality considerations in VLSI circuits
• Vertex sparsification in trees
• Vertex sparsifiers: new results from old techniques

Cited in

(5)

• The power of vertex sparsifiers in dynamic graph algorithms
• Vertex Sparsifiers: New Results from Old Techniques
• Improved guarantees for vertex sparsification in planar graphs
• Refined vertex sparsifiers of planar graphs
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms

This page was built for publication: Improved guarantees for vertex sparsification in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5208743)