Refined vertex sparsifiers of planar graphs

DOI10.1137/17M1151225MaRDI QIDQ5208742zbMATH OpenWikidataFDO

Authors Robert Krauthgamer, Havana Rika

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.05951

zbMATH Keywords

cut sparsificationdistance sparsificationmimicking networksminimum terminal cutsplanar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We study the following version of cut sparsification. Given a large edge-weighted network $G$ with $k$ terminal vertices, compress it into a smaller network $H$ with the same terminals, such that every minimum terminal cut in $H$ approximates the corresponding one in $G$, up to a factor $qgeq1$ that is called the quality. (The case $q=1$ is known also as a mimicking network). We provide new insights about the structure of minimum terminal cuts, leading to new results for cut sparsifiers of planar graphs. Our first contribution identifies a subset of the minimum terminal cuts, which we call elementary, that generates all the others. Consequently, $H$ is a cut sparsifier if and only if it preserves all the elementary terminal cuts (up to this factor $q$). This structural characterization lead to improved bounds on the size of $H$. For example, it improve the bound of mimicking-network size for planar graphs into a near-optimal one. Our second and main contribution is to refine the known bounds in terms of $gamma=gamma(G)$, which is defined as the minimum number of faces that are incident to all the terminals in a planar graph $G$. We prove that the number of elementary terminal cuts is $O((2k/gamma{)}^{2gamma})$ (compared to $O(2^k)$ terminal cuts), and furthermore obtain a mimicking-network of size $O(gamma{2}^{2gamma}{k}^4)$, which is near-optimal as a function of $gamma$. In the analysis we break the elementary terminal cuts into fragments, and count them carefully. Our third contribution is a duality between cut sparsification and distance sparsification for certain planar graphs, when the sparsifier $H$ is required to be a minor of $G$. This duality connects problems that were previously studied separately, implying new results, new proofs of known results, and equivalences between open gaps.

Recommendations

• Improved guarantees for vertex sparsification in planar graphs
• Improved guarantees for vertex sparsification in planar graphs
• An exponential lower bound for cut sparsifiers in planar graphs
• An exponential lower bound for cut sparsifiers in planar graphs
• Vertex Sparsifiers: New Results from Old Techniques

Cites work

• A face cover perspective to ℓ₁ embeddings of planar graphs
• A simple algorithm for multicuts in planar graphs with outer terminals
• A Tight Lower Bound for the Steiner Point Removal Problem on Trees
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• An exponential lower bound for cut sparsifiers in planar graphs
• An Optimal Synchronizer for the Hypercube
• 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
• Computing mimicking networks
• Cutting Corners Cheaply, or How to Remove Steiner Points
• Efficient algorithms for \(k\)-terminal cuts on planar graphs
• Extensions and limits to vertex sparsification
• Flow-Cut Gaps and Face Covers in Planar Graphs
• Flow-cut gaps for integer and fractional multiflows
• Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
• scientific article; zbMATH DE number 5485537 (Why is no real title available?)
• Improved guarantees for vertex sparsification in planar graphs
• Metric extension operators, vertex sparsifiers and Lipschitz extendability
• Mimicking Networks and Succinct Representations of Terminal Cuts
• Multicommodity flows in planar graphs
• On mimicking networks representing minimum terminal cuts
• On the Complexity of Covering Vertices by Faces in a Planar Graph
• On the geometry of graphs with a forbidden minor
• On vertex sparsifiers with Steiner nodes
• Planar graph decomposition and all pairs shortest paths
• Randomized approximation schemes for cuts and flows in capacitated graphs
• Shortest path queries in planar graphs
• 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
• Towards \((1 + \varepsilon)\)-approximate flow sparsifiers
• Vertex sparsification in trees
• Vertex sparsifiers: new results from old techniques

Cited in

(11)

• An exponential lower bound for cut sparsifiers in planar graphs
• On mimicking networks representing minimum terminal cuts
• Steiner point removal with distortion \(O(\log k)\) using the \texttt{Relaxed-Voronoi} algorithm
• Improved guarantees for vertex sparsification in planar graphs
• An exponential lower bound for cut sparsifiers in planar graphs
• Improved guarantees for vertex sparsification in planar graphs
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• On quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems
• O(1) Steiner point removal in series-parallel graphs
• A face cover perspective to _1 embeddings of planar graphs
• Scattering and sparse partitions, and their applications

This page was built for publication: Refined vertex sparsifiers of planar graphs

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