Multi-Level Graph Sketches via Single-Level Solvers

Understand

Given an undirected weighted graph $G(V,E)$, a constrained sketch over a terminal set $T\subset V$ is a subgraph $G'$ that connects the terminal vertices while satisfying a given set of constraints.

• Examples include Steiner trees (preserving connectivity among $T$) and subsetwise spanners (preserving shortest path distances up to a stretch factor).
• Multi-level constrained terminal sketches are generalizations in which terminal vertices require different levels or grades of service and each terminal pair is connected with edges of at least the minimum required level of the two terminals.
• This paper gives a flexible procedure for computing a broad class of multi-level graph sketches, which encompasses multi-level graph spanners, Steiner trees, and $k$--connected subgraphs as a few special cases.