Factorization and pseudofactorization of weighted graphs

DOI10.1016/J.DAM.2023.04.019MaRDI QIDQ6162029zbMATH OpenFDO

Authors Kristin Sheridan, Joseph Berleant, Mark Bathe, Anne Condon, Virginia Vassilevska Williams

Publication date 15 June 2023

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.06990

zbMATH Keywords

graph embeddingsgraph factorizationisometric embeddingsmetric spacesweighted graphs

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Abstract: For unweighted graphs, finding isometric embeddings is closely related to decompositions of $G$ into Cartesian products of smaller graphs. When $G$ is isomorphic to a Cartesian graph product, we call the factors of this product a factorization of $G$. When $G$ is isomorphic to an isometric subgraph of a Cartesian graph product, we call those factors a pseudofactorization of $G$. 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 $G$, where $G$ 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 $m$-edge, $n$-vertex graph with positive integer edge weights can be factored in $O(m^2)$ time, plus the time to find all pairs shortest paths (APSP) distances in a weighted graph, resulting in an overall running time of $O(m^2+n^{2}loglogn)$ time. We also show that a pseudofactorization for such a graph can be computed in $O(mn)$ time, plus the time to solve APSP, resulting in an $O(mn+n^{2}loglogn)$ running time.

Recommendations

• Isometric Hamming embeddings of weighted graphs
• Metrization of weighted graphs
• Faster isometric embedding in products of complete graphs
• An exact algorithm for minimum distortion embedding
• Metric embedding via shortest path decompositions

Cites work

• A new approach to all-pairs shortest paths on real-weighted graphs
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Distance-preserving subgraphs of hypercubes
• Factoring a graph in polynomial time
• Geometry of cuts and metrics
• Graph multiplication
• scientific article; zbMATH DE number 4012654 (Why is no real title available?)
• Isometric embedding in products of complete graphs
• Isometric embeddings in Hamming graphs
• Isometric Hamming embeddings of weighted graphs
• On Isometric Embeddings of Graphs
• On the Addressing Problem for Loop Switching
• On the complexity of recognizing Hamming graphs and related classes of graphs
• Product graph representations
• Recognizing Cartesian products in linear time

Cited in

(2)

• Factorization-Based Graph Repartitionings
• Testing whether a subgraph is convex or isometric

This page was built for publication: Factorization and pseudofactorization of weighted graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6162029)