Sheridan Kristin, Berleant Joseph, Bathe Mark, Condon Anne, Williams Virginia Vassilevska
Department of of Computer Science, University of Texas, Austin, TX.
Department of Biological Engineering, Massachusetts Institute of Technology, Cambridge, MA.
Discrete Appl Math. 2023 Oct 15;337:81-105. doi: 10.1016/j.dam.2023.04.019. Epub 2023 May 8.
For unweighted graphs, finding isometric embeddings of a graph is closely related to decompositions of into Cartesian products of smaller graphs. When is isomorphic to a Cartesian graph product, we call the factors of this product a factorization of . When is isomorphic to an isometric subgraph of a Cartesian graph product, we call those factors a pseudofactorization of . Prior work has shown that an unweighted graph's pseudofactorization can be used to generate a canonical isometric embedding into a product of the smallest possible pseudofactors. However, for arbitrary weighted graphs, which represent a richer variety of metric spaces, methods for finding isometric embeddings or determining their existence remain elusive, and indeed pseudofactorization and factorization have not previously been extended to this context. In this work, we address the problem of finding the factorization and pseudofactorization of a weighted graph , where satisfies the property that every edge constitutes a shortest path between its endpoints. We term such graphs minimal graphs, noting that every graph can be made minimal by removing edges not affecting its path metric. We generalize pseudofactorization and factorization to minimal graphs and develop new proof techniques that extend the previously proposed algorithms due to Graham and Winkler [Graham and Winkler, '85] and Feder [Feder, '92] for pseudofactorization and factorization of unweighted graphs. We show that any -vertex, -edge graph with positive integer edge weights can be factored in time, plus the time to find all pairs shortest paths (APSP) distances in a weighted graph, resulting in an overall running time of time. We also show that a pseudofactorization for such a graph can be computed in time, plus the time to solve APSP, resulting in an running time.
对于无权图，找到图的等距嵌入与将其分解为较小图的笛卡尔积密切相关。当图同构于笛卡尔图积时，我们称该积的因子为图的一种分解。当图同构于笛卡尔图积的等距子图时，我们称这些因子为图的伪分解。先前的工作表明，无权图的伪分解可用于生成到尽可能小的伪因子积中的规范等距嵌入。然而，对于表示更丰富度量空间种类的任意加权图，找到等距嵌入或确定其存在的方法仍然难以捉摸，实际上伪分解和分解此前尚未扩展到这种情况。在这项工作中，我们解决了找到加权图(G)的分解和伪分解的问题，其中(G)满足每条边构成其端点之间最短路径的性质。我们将这样的图称为最小图，注意到通过去除不影响其路径度量的边，每个图都可以变为最小图。我们将伪分解和分解推广到最小图，并开发了新的证明技术，扩展了先前由格雷厄姆和温克勒[格雷厄姆和温克勒，'85]以及费德[费德，'92]提出的用于无权图伪分解和分解的算法。我们表明，任何具有正整数边权重的(n)顶点、(m)边图都可以在(O(n^2m))时间内进行分解，再加上在加权图中找到所有对最短路径（APSP）距离的时间，导致总运行时间为(O(n^2m))时间。我们还表明，对于这样的图，可以在(O(n^2m))时间内计算出伪分解，再加上解决APSP的时间，导致运行时间为(O(n^2m))时间。
