Search

For unweighted graphs, finding isometric embeddings of a graph G 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 n -vertex, m -edge 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  log log  n ) time. We also show that a pseudofactorization for such a graph can be computed in O ( m n ) time, plus the time to solve APSP, resulting in an O ( m n + n 2  log log  n ) running time., Competing Interests: Declarations of Interest The authors declare that they have no competing interests.

A mapping α : V ( G ) → V ( H ) from the vertex set of one graph G to another graph H is an isometric embedding if the shortest path distance between any two vertices in G equals the distance between their images in H . Here, we consider isometric embeddings of a weighted graph G into unweighted Hamming graphs, called Hamming embeddings, when G satisfies the property that every edge is a shortest path between its endpoints. Using a Cartesian product decomposition of G called its canonical isometric representation , we show that every Hamming embedding of G may be partitioned into a canonical partition , whose parts provide Hamming embeddings for each factor of the canonical isometric representation of G . This implies that G permits a Hamming embedding if and only if each factor of its canonical isometric representation is Hamming embeddable. This result extends prior work on unweighted graphs that showed that an unweighted graph permits a Hamming embedding if and only if each factor is a complete graph. When a graph G has nontrivial isometric representation, determining whether G has a Hamming embedding can be simplified to checking embeddability of two or more smaller graphs., Competing Interests: Declaration of competing interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Patients with severe aplastic anemia (SAA) can have an unrecognized inherited bone marrow failure syndrome (IBMFS) because of phenotypic heterogeneity. We curated germline genetic variants in 104 IBMFS-associated genes from exome sequencing performed on 732 patients who underwent hematopoietic cell transplant (HCT) between 1989 and 2015 for acquired SAA. Patients with pathogenic or likely pathogenic (P/LP) variants fitting known disease zygosity patterns were deemed unrecognized IBMFS. Carriers were defined as patients with a single P/LP variant in an autosomal recessive gene or females with an X-linked recessive P/LP variant. Cox proportional hazard models were used for survival analysis with follow-up until 2017. We identified 113 P/LP single-nucleotide variants or small insertions/deletions and 10 copy number variants across 42 genes in 121 patients. Ninety-one patients had 105 in silico predicted deleterious variants of uncertain significance (dVUS). Forty-eight patients (6.6%) had an unrecognized IBMFS (33% adults), and 73 (10%) were carriers. No survival difference between dVUS and acquired SAA was noted. Compared with acquired SAA (no P/LP variants), patients with unrecognized IBMFS, but not carriers, had worse survival after HCT (IBMFS hazard ratio [HR], 2.13; 95% confidence interval[CI], 1.40-3.24; P = .0004; carriers HR, 0.96; 95% CI, 0.62-1.50; P = .86). Results were similar in analyses restricted to patients receiving reduced-intensity conditioning (n = 448; HR IBMFS = 2.39; P = .01). The excess mortality risk in unrecognized IBMFS attributed to death from organ failure (HR = 4.88; P < .0001). Genetic testing should be part of the diagnostic evaluation for all patients with SAA to tailor therapeutic regimens. Carriers of a pathogenic variant in an IBMFS gene can follow HCT regimens for acquired SAA., (© 2022 by The American Society of Hematology.)