View article

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 , and if is planar, then the size of improves to . We complement our upper bound by showing that there exists an infinite family of grids such that any RPM must have vertices. (2) Given a weighted undirected graph and terminal vertices with , an …