2026/07/23 by Arnold Filtser, Hung Le, Nikolas Mählmann +2
#math.CO #cs.DM #cs.DS #math.MG
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 δ-fat minor, for some δ>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 α≥ β large enough compared to δ, in every large enough set A in G one can find a sizable subset B that becomes α-scattered after removing a bounded number of balls of radius β. We call this property drill-flatness. Notably, the proof only relies on excluding shallow fat minors: every branch set has radius at most 2α. As a corollary, we prove that metric graphs that exclude a fixed δ-fat minor have bounded ε-scatter dimension if we consider only ε-scatters at distances large enough compared to δ. 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 δ-fat minor admits an approximation algorithm that finds a solution of cost at most (1+ε)\cdotOPT+\cal O(δ/ε2) in time \cal OH,ε(n^\cal 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.