Bounding $\epsilon$-scatter dimension via metric sparsity

Abstract

A recent work of Abbasi et al. [FOCS 2023] introduced the notion of $\epsilon$-scatter dimension of a metric space and showed a general framework for efficient parameterized approximation schemes (so-called EPASes) for a wide range of clustering problems in classes of metric spaces that admit a bound on the $\epsilon$-scatter dimension. Our main result is such a bound for metrics induced by graphs from any fixed proper minor-closed graph class. The bound is double-exponential in ${\epsilon }^{-1}$ and the Hadwiger number of the graph class and is accompanied by a nearly tight lower bound that holds even in graph classes of bounded treewidth. On the way to the main result, we introduce metric analogs of well-known graph invariants from the theory of sparsity, including generalized coloring numbers and flatness (aka uniform quasi-wideness), and show bounds for these invariants in proper minor-closed graph classes. Finally, we show the power of newly introduced toolbox by showing a coreset for $k$-Center in any proper minor-closed graph class whose size is polynomial in $k$ (but the exponent of the polynomial depends on the graph class and ${\epsilon }^{-1}$).

Full version of a paper accepted to SODA 2025