Cut Tree Structures with Applications on Contraction-Based Sparsification

On-Hei Solomon Lo, Jens M. Schmidt

We introduce three new cut tree structures of graphs $G$ in which the vertex set of the tree is a partition of $V(G)$ and contractions of tree vertices satisfy sparsification requi…