Summary: We study vertex cut and flow sparsifiers that were recently introduced by A. Moitra [in: 2009 IEEE 50th annual symposium on foundations of computer science – FOCS 2009. Proceedings of the symposium, Atlanta, GA, USA, October 24–27, 2009. Los Alamitos, CA: IEEE Computer Society. 3–12 (2009; Zbl 1292.05251)], and T. Leighton and A. Moitra [in: Proceedings of the 42nd annual ACM symposium on theory of computing, STOC ’10. Cambridge, MA, USA, June 5–8, 2010. New York, NY: Association for Computing Machinery (ACM). 47–56 (2010; Zbl 1293.05149)]. We improve and generalize their results. We give a new polynomial-time algorithm for constructing \(O(\log k/ \log \log k)\) cut and flow sparsifiers, matching the best known existential upper bound on the quality of a sparsifier, and improving the previous algorithmic upper bound of \(O(\log^{2}k/ \log \log k)\). We show that flow sparsifiers can be obtained from linear operators approximating minimum metric extensions. We introduce the notion of (linear) metric extension operators, prove that they exist, and give an exact polynomial-time algorithm for finding optimal operators.
We then establish a direct connection between flow and cut sparsifiers and Lipschitz extendability of maps in Banach spaces, a notion studied in functional analysis since 1930s. Using this connection, we obtain a lower bound of \(\Omega \left( {\sqrt {\log k/\log \log k} } \right)\) for flow sparsifiers and a lower bound of \(\Omega \left( {\sqrt {\log k} /\log \log k} \right)\) for cut sparsifiers. We show that if a certain open question posed by K. Ball [Geom. Funct. Anal. 2, No. 2, 137–172 (1992; Zbl 0788.46050)] has a positive answer, then there exist \(\tilde O\left( {\sqrt {\log k} } \right)\) cut sparsifiers. On the other hand, any lower bound on cut sparsifiers better than \(\tilde \Omega \left( {\sqrt {\log k} } \right)\) would imply a negative answer to this question.