Factorization and pseudofactorization of weighted graphs

Abstract

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\left(m^2\right)$ time, plus the time to find all pairs shortest paths (APSP) distances in a weighted graph, resulting in an overall running time of $O\left(m^2+n^2\text{log log}n\right)$ time. We also show that a pseudofactorization for such a graph can be computed in $O\left(mn\right)$ time, plus the time to solve APSP, resulting in an $O\left(mn+n^2\text{log log}n\right)$ running time.

Figure 1:

A schematic showing how hypercube embeddings can be used to construct a set of DNA sequences with a particular relationship. a) An unweighted graph representing the desired binding strength relationships between DNA strands. b) A hypercube embedding (equivalent to an assignment of binary strings) of this graph. c-d) Each binary string in the hypercube embedding corresponds to a DNA sequence, by associating 0 and 1 with point mutations within a sequence. When mutations are not adjacent and the pre- and post-mutation bases are chosen carefully, the binding strength between DNA strands is approximately determined by the number of mutations between one strand and the complement of the other. This relationship can be captured in a hypercube or Hamming graph.

Figure 2:

The graph on the right is the Cartesian product of the graphs on the left. The parent edge of a given edge in the product graph is the edge in a factor that has the same color as it. For example, edges $\left(a,x\right)\left(a,y\right)$, $\left(b,x\right)\left(b,y\right)$, and $\left(c,x\right)\left(c,y\right)$ in the product graph all have edge $xy$ in the second factor as their parent edge. Here, edges of the same color have the same weight.

Figure 3:

Subfigure (a) shows a non-prime, non-irreducible graph. Subfigure (b) shows the prime factorization of the graph in (a). Subfigure (c) shows the canonical pseudofactorization of the graph in (a).

Figure 4:

A generalization of pseudofactorization to weighted graphs must be done with care. For example, if pseudofactorization requires only that the input graph is isometrically embeddable into a Cartesian graph product, then even graphs such as $K_2$ have no irreducible pseudofactorization. We require that a graph also be isomorphic to a subgraph of the Cartesian graph product, which precludes this example.

Figure 5:

An unweighted graph (left) and a minimal weighted graph with the same vertex adjacency (right). Edges that are the same color are members of the same equivalence class under ${\theta }^{\text{*}}$. The graph on the left has two equivalence classes and it is not irreducible, while the graph on the right has only one equivalence class and is irreducible.

Figure 6:

If $u{v}^{\prime }\theta vx$ and $uv\theta v^{\prime }x$, then existence of the subgraph depicted here implies that $uv$ and $u{v}^{\prime }$ satisfy the square property.

Figure 7:

Illustration of Algorithm 1 on a weighted graph of six nodes. (a) The algorithm first finds the equivalence classes of ${\theta }^{\text{*}}$, shown here with distinct colors. The algorithm then considers the remaining graph when each equivalence class is removed and uses that to construct the final output graphs. In this case, there are three ${\theta }^{\text{*}}$ equivalence classes and thus three pseudofactors. (b) This subfigure shows in the first panel the same graph as in (a), in the second panel it shows its irreducible pseudofactorization, and in the third panel it shows Cartesian product of those pseudofactors, of which the original graph is an isometric subgraph.

Figure 8:

Paths described in the proof of Lemma 3.4. (a) A graph in which $u\in C_a$ has an edge to distinct $v$, $v^{\prime }\in C_b$, which the proof of Lemma 3.4 shows is impossible. (b) Definitions of $Q_a$ and $Q_b$ from the proof when considering $u\in C_a$, $v\in C_b$.

Figure 9:

A visualization of the path constructed in the proof of Theorem 3.9. (a) Each $C_i$ is a connected component in $G_k^{\prime }$, where $E_k$ is the equivalence class we consider in the theorem. Starting at $u$, we construct a path $Q_0$ through edges in $C_0$ to $x_0^1$, which is some vertex in $C_0$ with an edge to $C_1$. We similarly construct $Q_1$ from $x_1^1$ to $x_1^2$ and so on. The path $Q_2\cdots Q_{n-2}$ is the concatenation of the paths through connected components $C_2$ through $C_{n-2}$. (b) Part of $G_k^{\text{*}}$ for the graph in (a). We have ${\pi }_k\left(u\right)=q_0$ and ${\pi }_k\left(v\right)=q_n$, and the path $Q^{\text{*}}=\left(q_0,q_1,\dots ,q_n\right)$ is an arbitrary path from ${\pi }_k\left(u\right)$ to ${\pi }_k\left(v\right)$ through $G_k^{\text{*}}$. The theorem shows that because of how $G_k^{\text{*}}$ is constructed, there must exist a path in $G$ like the one shown in (a), where the only edges in $E_k$ are the $x_{j-1}^j{x}_j^j$ and the weight of each $x_{j-1}^j{x}_j^j$ in $G$ is the same weight as $q_{j-1}{q}_j$ in $G_k^{\text{*}}$. (c) An example of this process applied to the graph from Figure 7, when considering the green pseudofactor shown on the right. Edge weights are omitted for simplicity. When the graph on the left is isometrically embedded into the product of its pseudofactors (see Figure 7b) with isometric embedding $\pi$, ${\pi }_k\left(u\right)=q_0$ and ${\pi }_k\left(v\right)=q_1$. We let $Q^{\text{*}}=\left(q_0,q_1\right)$. When constructing $Q$, we can select $Q_0$ to be $\left(u\right)$ (so $x_0^1=u$) and $Q_1$ to be $\left(x_1^1,v\right)$. Alternatively, we could select $Q_0$ to be $\left(u,y_0^1\right)$ and $Q_1$ to be $\left(v\right)$ (so $v=y_1^1$). Thus, although existence of the path $Q$ is guaranteed, $Q$ is not necessarily unique.

Figure 10:

a) A weighted graph $G$. b) $G_{\theta }$. c) $G$ with edges colored according to their equivalence class under ${\theta }^{\text{*}}$. Each equivalence class corresponds to a connected component of $G_{\theta }$. d-f) Analogous illustration for the graph shown in (d).

Figure 11:

(a) An input graph $G$. (b) $G_{\theta }$. (c) $G$ with a spanning tree $T$ (edges not in $T$ are in gray). (d) $G_{{\theta }_T}$. The black and gray outlines indicate if each edge is in spanning tree $T$ or not, respectively. The graph is the subgraph of $G_{\theta }$ with only those edges incident to an element of $T$. (e) For this choice of $T$, $G_{\theta }$ and $G_{{\theta }_T}$ produce the same equivalence classes on the edges of $G$.