Vertex Sparsification in Trees

Gramoz Goranci, Harald Raecke

Given an unweighted tree $T=(V,E)$ with terminals $K\subset V$, we show how to obtain a $2$-quality vertex flow and cut sparsifier $H$ with $V_H=K$. We prove that our result is…