Vertex sparsification in trees

DOI10.1007/978-3-319-51741-4_9MaRDI QIDQ2971161zbMATH OpenOpenAlexFDO

Authors Gramoz Goranci, Harald Räcke

Publication date 4 April 2017

Published in Approximation and Online Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

graph sparsificationtreesvertex flow sparsifiers

Mathematics Subject Classification ID

Trees (05C05) Flows in graphs (05C21)

Abstract: Given an unweighted tree $T=(V,E)$ with terminals $KsubsetV$, we show how to obtain a $2$-quality vertex flow and cut sparsifier $H$ with $V_H=K$. We prove that our result is essentially tight by providing a $2-o(1)$ lower-bound on the quality of any cut sparsifier for stars. In addition we give improved results for quasi-bipartite graphs. First, we show how to obtain a $2$-quality flow sparsifier with $V_H=K$ for such graphs. We then consider the other extreme and construct exact sparsifiers of size $O(2^k)$, when the input graph is unweighted.

Recommendations

• On vertex sparsifiers with Steiner nodes
• Vertex Sparsifiers: New Results from Old Techniques
• Vertex sparsifiers: new results from old techniques
• Vertex sparsification and oblivious reductions
• Extensions and limits to vertex sparsification

Cites work

• 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
• Cutting Corners Cheaply, or How to Remove Steiner Points
• Extensions and limits to vertex sparsification
• Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
• Hardness of robust network design
• scientific article; zbMATH DE number 5485537 (Why is no real title available?)
• scientific article; zbMATH DE number 1256718 (Why is no real title available?)
• Metric extension operators, vertex sparsifiers and Lipschitz extendability
• On mimicking networks representing minimum terminal cuts
• On vertex sparsifiers with Steiner nodes
• Spectral sparsification of graphs
• Steiner points in tree metrics don't (really) help

Cited in

(10)

• Improved guarantees for tree cut sparsifiers
• Near-optimal distance emulator for planar graphs
• Improved guarantees for vertex sparsification in planar graphs
• Refined vertex sparsifiers of planar graphs
• Improved guarantees for vertex sparsification in planar graphs
• On vertex sparsifiers with Steiner nodes
• Graph-Theoretic Concepts in Computer Science
• Vertex Sparsifiers: New Results from Old Techniques
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• Cut-preserving vertex sparsifiers for planar and quasi-bipartite graphs

This page was built for publication: Vertex sparsification in trees

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