# Approximation algorithms and an integer program for multi-level graph spanners

arXiv: https://arxiv.org/abs/1904.01135 · HTML: https://mlsanity.com/paper/1904.01135/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Apr 2019.

## Built on by (most cited first, 1 of 1)

- [Graph Sparsifications using Neural Network Assisted Monte Carlo Tree Search](https://mlsanity.com/paper/2311.10316/) (2023)

## Abstract (arXiv)

Given a weighted graph G(V,E) and t ≥ 1, a subgraph H is a t--spanner of G if the lengths of shortest paths in G are preserved in H up to a multiplicative factor of t. The subsetwise spanner problem aims to preserve distances in G for only a subset of the vertices. We generalize the minimum-cost subsetwise spanner problem to one where vertices appear on multiple levels, which we call the multi-level graph spanner (MLGS) problem, and describe two simple heuristics. Applications of this problem include road/network building and multi-level graph visualization, especially where vertices may require different grades of service. We formulate a 0--1 integer linear program (ILP) of size O(|E||V|2) for the more general minimum pairwise spanner problem, which resolves an open question by Sigurd and Zachariasen on whether this problem admits a useful polynomial-size ILP. We extend this ILP formulation to the MLGS problem, and evaluate the heuristic and ILP performance on random graphs of up to 100 vertices and 500 edges.