Improved guarantees for vertex sparsification in planar graphs

Goranci G, Henzinger MH, Peng P. 2020. Improved guarantees for vertex sparsification in planar graphs. SIAM Journal on Discrete Mathematics. 34(1), 130–162.

Download (ext.)

Journal Article | Published | English

Scopus indexed
Author
Goranci, Gramoz; Henzinger, MonikaISTA ; Peng, Pan
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 𝐺=(𝑉,𝐸) and terminal vertices πΎβŠ‚π‘‰ with |𝐾|=π‘˜, a (vertex) reachability sparsifier of 𝐺 is a digraph 𝐻=(𝑉𝐻,𝐸𝐻), πΎβŠ‚π‘‰π» that preserves all reachability information among terminal pairs. Let |𝑉𝐻| denote the size of 𝐻. In this work we introduce the notion of reachability-preserving minors (RPMs), i.e., we require 𝐻 to be a minor of 𝐺. We show any directed graph 𝐺 admits an RPM 𝐻 of size 𝑂(π‘˜3), and if 𝐺 is planar, then the size of 𝐻 improves to 𝑂(π‘˜2logπ‘˜). We complement our upper bound by showing that there exists an infinite family of grids such that any RPM must have Ξ©(π‘˜2) vertices. (2) Given a weighted undirected graph 𝐺=(𝑉,𝐸) and terminal vertices 𝐾 with |𝐾|=π‘˜, an exact (vertex) cut sparsifier of 𝐺 is a graph 𝐻 with πΎβŠ‚π‘‰π» that preserves the value of minimum cuts separating any bipartition of 𝐾. We show that planar graphs with all the π‘˜ terminals lying on the same face admit exact cut sparsifiers of size 𝑂(π‘˜2) that are also planar. Our result extends to flow and distance sparsifiers. It improves the previous best-known bound of 𝑂(π‘˜222π‘˜) for cut and flow sparsifiers by an exponential factor and matches an Ξ©(π‘˜2) lower-bound for this class of graphs.
Publishing Year
Date Published
2020-01-01
Journal Title
SIAM Journal on Discrete Mathematics
Publisher
Society for Industrial & Applied Mathematics
Volume
34
Issue
1
Page
130-162
ISSN
eISSN
IST-REx-ID

Cite this

Goranci G, Henzinger MH, Peng P. Improved guarantees for vertex sparsification in planar graphs. SIAM Journal on Discrete Mathematics. 2020;34(1):130-162. doi:10.1137/17m1163153
Goranci, G., Henzinger, M. H., & Peng, P. (2020). Improved guarantees for vertex sparsification in planar graphs. SIAM Journal on Discrete Mathematics. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/17m1163153
Goranci, Gramoz, Monika H Henzinger, and Pan Peng. β€œImproved Guarantees for Vertex Sparsification in Planar Graphs.” SIAM Journal on Discrete Mathematics. Society for Industrial & Applied Mathematics, 2020. https://doi.org/10.1137/17m1163153.
G. Goranci, M. H. Henzinger, and P. Peng, β€œImproved guarantees for vertex sparsification in planar graphs,” SIAM Journal on Discrete Mathematics, vol. 34, no. 1. Society for Industrial & Applied Mathematics, pp. 130–162, 2020.
Goranci G, Henzinger MH, Peng P. 2020. Improved guarantees for vertex sparsification in planar graphs. SIAM Journal on Discrete Mathematics. 34(1), 130–162.
Goranci, Gramoz, et al. β€œImproved Guarantees for Vertex Sparsification in Planar Graphs.” SIAM Journal on Discrete Mathematics, vol. 34, no. 1, Society for Industrial & Applied Mathematics, 2020, pp. 130–62, doi:10.1137/17m1163153.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 1702.01136

Search this title in

Google Scholar