Improved guarantees for vertex sparsification in planar graphs

DOI10.1137/17M1163153zbMATH Open1431.05047arXiv1702.01136WikidataQ126385123 ScholiaQ126385123MaRDI QIDQ5208743FDOQ5208743

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)

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.

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

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

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)

Cites Work

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

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)