Some General Structure for Extremal Sparsification Problems

01/21/2020

∙

by   Greg Bodwin, et al.

∙

0

∙

share

This paper is about a branch of theoretical computer science that studies how much graphs can be sparsified while faithfully preserving their properties. Examples include spanners, distance preservers, reachability preservers, etc. We introduce an abstraction that captures all of the above, and then we prove a couple simple structural lemmas about this abstraction. These imply unified proofs of some state-of-the-art results in the area, and they improve the size of Chechik's +4 additive spanner [SODA '13] from O(n^7/5) to O(n^7/5).