Fatness and Flatness

Abstract

Fat minors are the metric analog of graph minors that are tailored to the analysis of metric (edge-weighted) graphs and, more generally, metric spaces having a suitable notion of shortest paths. Despite a large interest in this notion, not much is known about the structure of metric graphs excluding a fixed fat minor. We prove that if a metric graph $G$ excludes a fixed graph $H$ as a $\hat{I}´$-fat minor, for some $\hat{I}´>0$, then $G$ enjoys the metric analog of flatness (aka uniform quasi-wideness) - a structural property from the field of Sparsity. In essence, our flatness result says that for any $\hat{I}\pm \ge {\hat{I}}^2$ large enough compared to $\hat{I}´$, in every large enough set $A$ in $G$ one can find a sizable subset $B$ that becomes $\hat{I}\pm$-scattered after removing a bounded number of balls of radius ${\hat{I}}^2$. We call this property drill-flatness. Notably, the proof only relies on excluding shallow fat minors: every branch set has radius at most $2\hat{I}\pm$. As a corollary, we prove that metric graphs that exclude a fixed $\hat{I}´$-fat minor have bounded $\epsilon$-scatter dimension if we consider only $\epsilon$-scatters at distances large enough compared to $\hat{I}´$. By combining this with the results of Abbasi et al. [FOCS 2023], we infer that the $k$-Center problem on instances excluding $H$ as a $\hat{I}´$-fat minor admits an approximation algorithm that finds a solution of cost at most $(1+\epsilon )\cdot \mathsf{OPT}+\mathcal{O}(\hat{I}´/{\epsilon }^2)$ in time ${\mathcal{O}}_{H,\epsilon }(n^{\mathcal{O}(1)})$. This is one of the first algorithmic results for general fat-minor-free metrics. We also study drill-flatness in hereditary classes of (unweighted) graphs, where we obtain a characterization equating drill-flatness with excluding shallow induced minors. This is an induced analog of the equivalence between flatness and nowhere denseness - one of central results of Sparsity.

37 pages, 9 figures. Abstract shortened to meet arXiv's constraints