Graphs with bounded partitions admit precise simplified representations
Additive Quasi-isometry via rooted graph partitions and layering partition
Discrete Mathematics
Summary
This paper studies when one complex network can be closely approximated by a simpler network, where distances between points are preserved up to a small fixed amount. The authors show that if a graph and certain variations of another have limited complexity in how shortest paths behave, and the first graph can be nicely divided based on the second, then there is a simpler graph similar enough to the first one. They also answer an open question about networks that avoid certain complicated subgraphs, proving these can be approximated well by simpler networks with the same kind of restrictions.
What this means in practice
- •For network designers: Simplify complex network topologies while preserving distances within a controlled additive error using bounded graph partitions.
- •For database query optimizers: Optimize query plans by approximating complex graph join structures with simpler graphs of bounded treewidth and additive distortion.
A theory result. No direct application yet.
Authors
Dibyayan Chakraborty, Yann Vaxès
Abstract
For a graph $H$, $\langle H \rangle$ denotes the class of all subdivisions of $H$ and $tw(H)$ denotes the treewidth of $H$. In this paper, we prove the following. For $k\geq 1, R\geq 1$, let $G,H$ be two graphs such that strong isometric path complexities (Chakraborty et al. [\textsc{Disc. Math., 2026}]) of both $G$ and $\langle H \rangle$ are at most $k$, and $G$ admits an honest, ``nicely rooted'' $R$-bounded $H$-partition. Then, there is a graph $F$ with $tw(F)\leq tw(H)$ such that $G$ admits a $(1,33\cdot R\cdot k^2)$-quasi-isometry to $F$. Using results of Albrechtsen, Distel, and Georgakopoulos (2025), we also obtain that $K_{2,t}$-asymptotic minor-free graphs admit quasi-isometries with additive distortion to $K_{2,t}$-minor-free graphs. This answers an open question raised by the above authors. As part of our proof, we combine the graph-partition based method and the layering partition based method (Chepoi et al. [\textsc{Discrete Comput. Geom.} 2012]) to obtain additive quasi-isometry when both the source and all subdivisions of the target graph have bounded strong isometric path complexity.