Shortest Paths in Multimode Graphs

The study of shortest paths algorithms in directed graphs has introduced various distance measures. The most standard notion of distance between two vertices $u$ and $v$ is the minimum length of a path from $u$ to $v$, $d(u,v)$. This asymmetric one-way notion of distance is not always the most natural. In some applications the roundtrip distance $d(u,v)+d(v,u)$, defined by Cowen and Wagner [8], is most useful, since unlike its one-way counterpart, it is a metric.

In directed acyclic graphs (DAGs), however, both the standard notion of distance and the roundtrip notion produce infinite distances for all or a large fraction of the distance pairs. A more useful notion of distance in this case was defined by Abboud, Vassilevska W. and Wang [1]. In this work they introduced the min-distance, defined as $d_{\text{min}}(u,v)=\min \{d(u,v),d(v,u)\}$. Under one-way distance or roundtrip distance, almost all points in a DAG have infinite eccentricity. Introducing min-distance opened an avenue of research which lead to intricate algorithms for computing or approximating min-diameter, radius and eccentricities in DAGs [1, 9] as well as for general graphs [3, 7, 12].

One real-world motivation for studying the min-distance problem is computing the optimal location for a hospital, as one has the choice of either going to the hospital or having a doctor come to them. The min-distance therefore measures the fastest way to receive care and the point with smallest min-eccentricity in the graph functions as the optimal location for a hospital. Imagine now that the doctor can take a helicopter, whereas a patient can only take a cab to the doctor. Then the two routes are no longer part of the same graph - the routes by which a helicopter can travel are very different from those available to a taxi. The new distance between the patient and the doctor is now the minimum between the distances in two different graphs.

Consider another common scenario. We want to fly from city $A$ to city $B$. We can take any valid itinerary, except that each itinerary needs to stay within the same airline alliance. Now the fastest flight time is the minimum of the distances over several different “graphs”, one for each airline alliance. All of these graphs share a vertex set representing the different cities, while each graph has edges representing the flights of a single airline alliance.

Let us formalize a new shortest paths problem that captures both scenarios. Consider a collection of $k$ graphs over the same vertex set $V$. Let their edge sets be $E_1,\mathrm{\dots },E_k$. Together they form a “$k$-multimode graph” $𝒢=(V,E_1,\mathrm{\dots },E_k)$. One can associate each $E_i$ with a “mode of transportation”, where these modes are separate and cannot be combined.

The $k$-mode distance between two vertices $u,v\in V$ in a $k$-multimode graph $𝒢=(V,E_1,\mathrm{\dots }{E}_k)$ is defined as

where $d_{G_i}$ is the distance in the graph $G_i=(V,E_i)$. Intuitively, $d_{𝒢}(u,v)$ is the length of the shortest path connecting $u$ and $v$ using a single mode of transportation.

The $k$-mode distance naturally arises in practice in the context of multiple embeddings in machine learning (see [21, 15, 18] and many more). In many scenarios, given a high dimensional data set, there is no clear distance function that accurately captures semantic relationships within the data. To address this, deep learning is now commonly used to obtain a data embedding that encodes semantic information. As research in this field advances, we observe a proliferation of embeddings which can vary due to differences in network architecture, learning paradigms or training data, to name a few. This results in a single set of data points with multiple sets of edges representing distances in the different embeddings spaces. For every pair of points we are interested in the embedding in which they are closest together and often care about finding a pair of points which are furthest apart in all embeddings (i.e. computing the $k$-mode diameter) or a point which is closest to all others in some embedding (i.e. computing the $k$-mode radius).

Let us first consider the All-Pairs Shortest Paths (APSP) problem in $k$-multimode graphs on $n$ vertices: compute the $k$-mode distance between all pairs of vertices of $𝒢=(V,E_1,\mathrm{\dots }{E}_k)$. One can always run any APSP algorithm on each $(V,E_i)$ separately, resulting in a running time which is $k$ times that of the standard APSP algorithm. This approach will also trivially compute the $k$-mode radius of the multimode graph. In fact, we show that in general no algorithm can have polynomial improvements over this trivial solution.

While it is clear for APSP that one can compute all $k$-multimode distances by solving $k$ instances of APSP separately on each graph, it is no longer obvious how to solve $k$-multimode radius or diameter using algorithms that compute the radius or diameter in a standard graph.

To illustrate why the $k$-mode diameter is not directly related to the standard diameters of the individual graphs $G_1,\mathrm{\dots },G_k$, denote the diameter of $G_1=(V,E_1)$ by $D_1=D(G_1)$ and let $u_1,v_1\in V$ be such that $d_{G_1}(u_1,v_1)=D_1$. Similarly, denote the diameter of $G_2=(V,E_2)$ by $D_2=D(G_2)$ and let $u_2,v_2\in V$ be such that $d_{G_2}(u_2,v_2)=D_2$. We cannot merely take the minimum of $D_1,D_2$ to get the diameter in the multimode graph $𝒢=(V,E_1,E_2)$. This is because it could be that and so that the multimode distance between $u_1$ and $v_1$ is not $D_1$ but rather $d_{G_2}(u_1,v_1)$ and similarly for $u_2$ and $v_2$. The multimode diameter can be the distance between some completely different pair of vertices and thus can be arbitrarily smaller than both $D_1$ and $D_2$. It could even be the case that $D_1,D_2$ are infinite, while the multimode diameter $D(𝒢)$ is finite.

However, if we wish to compute the exact $k$-mode diameter or radius of a $k$-multimode undirected graph, we show that we can in fact use any algorithm for computing standard diameter or radius in a blackbox way.

The proofs of both Theorem 1 and Theorem 2 follows from a straightforward application of standard techniques. We therefore defer their proofs to the full version of this work. We instead turn our focus to approximating these parameters.

There exists a plethora of algorithms and conditional lower bounds for approximating diameter and radius under both the standard notion of (directed or undirected) distance and the min-distance measure [2, 1, 7, 9, 10, 11, 6, 16, 4, 13]. As the $k$-multimode distance generalizes both these distance measures, we would like to develop approximation algorithms and prove tight conditional lower bounds for approximating diameter and radius in the multimode setting as well.

The known fine-grained hardness results for the min-distance and standard diameter, radius and eccentricities would trivially carry over for the multimode distance case (as it generalizes both). We are thus interested in when stronger hardness is possible, and when similar approximation algorithms can be attained.

Devising approximation algorithms for the min-distance measure is particularly difficult and therefore significantly new techniques had to be developed over the standard diameter ones (see e.g. [12, 7, 9]). The main difficulty lies in the fact that the triangle inequality no longer holds: it could be that $d_{min}(u,v)=1$ and $d_{min}(v,w)=1$ but $d_{min}(u,w)=\mathrm{\infty }$, as in the graph with vertices $\{u,v,w\}$ and edges $\{(v,u),(v,w)\}$. This difficulty persists and is even more prominent in the multimode distance setting, as now the various graphs that represent modes of transportation may not share any edges. We can therefore expect that the distance parameters of interest can be even more difficult to approximate.

Let $G=(V,E)$ be a graph with $n=|V|$ vertices and $m=|E|$ edges. For a $k$-multimode graph $𝒢=(V,E_1,\mathrm{\dots },E_k)$, denote $n=|V|$ and $m=|E_1|+\mathrm{\dots },+|E_k|$, we will also use $e(𝒢)$ to denote the number of edges in $𝒢$. Define $G_i=(V,E_i)$ and for any $u,v\in V$ let $d_{G_i}(u,v)$ be the length of the shortest path from $u$ to $v$ in the graph $G_i$. When $𝒢$ is clear from context, we denote this distance by $d_i(u,v)$. The $k$-mode distance of $u,v$ is defined as $d_{𝒢}(u,v)={\min }_{i\in [k]}{d}_i(u,v)$.

Throughout this paper, we will often associate each “mode” with a color. We can assign a color to each set of edges $E_i$ and think of $𝒢$ as the graph $G=(V,E={\bigcup }_i{E}_i)$ where every edge is assigned at least one color. A path that uses a single mode corresponds to a monochromatic path under this coloring.

Consider the special case of $2$-multimode graphs with edge sets $E_1,E_2$. We use “red distance” to refer to $d_{G_1}$, meaning paths using only edges in $E_1$ (“red edges”). Likewise, we use “blue distance” to refer to $d_{G_2}$. In $3$-multimode graphs, $𝒢=(V,E_1,E_2,E_3)$, we use “green distance” to refer to $d_{G_3}$.

In this work we present many approximation algorithms to $k$-mode diameter, radius and eccentricities of $k$-multimode graphs. We define an $(\alpha ,\beta )$-approximation algorithm for a value $D$ to be such that outputs $\tilde{D}$ satisfying $D\le \tilde{D}\le \alpha D+\beta$. When $\beta =0$ we have a multiplicative approximation and call it an $\alpha$-approximation.

We call a directed $k$-multimode graph $𝒢=(V,E_1,\mathrm{\dots },E_k)$ a $k$-multimode DAG (Directed Acyclic Graph) if $G_1,\mathrm{\dots },G_k$ are all DAGs.

Denote the ball around a vertex $v$ in a graph $G$, or the neighborhood of $v$, by . In a $k$-multimode graph, we will use $B_i(v,r)$ to denote $B_{G_i}(v,r)$.

Given a vertex subset $A\subseteq V$, denote by $𝒢[A]$ the induced subgraph defined by $𝒢[A]≔(A,E_1\cap A\times A,\mathrm{\dots },E_k\cap A\times A)$.

The eccentricity of a vertex $v$ in a graph $G$ is defined as $ec{c}_G(u)≔{\max }_{v\in V}{d}_G(u,v)$. The diameter of $G$, or $D(G)$, is defined as the largest eccentricity in the graph and the radius, or $R(G)$, is defined as the smallest eccentricity. We naturally extend these definitions to $k$-multimode graphs using the $k$-mode distance. We refer to points $u,v$ such that $d_G(u,v)=D(G)$ as “diameter endpoints” and say that these points “achieve the diameter”. We refer to a point $c$ such that $ec{c}_G(c)=R(G)$ as a “center” of $G$.

The $k$-mode distance is a generalization of the well studied min-distance. In a directed graph, the min-distance between two vertices $u,v$ is defined as $d_{\min }(u,v)≔\min \{d(u,v),d(v,u)\}$. Approximating the diameter of a graph under the min-distance (or $\mathrm{𝗆𝗂𝗇}\text{-}\mathrm{𝖽𝗂𝖺𝗆}$) has been studied in [1], [7], [9], [12]. In our approximation algorithms we will use the following lemma from [1]:

A variant of the diameter that we use throughout this paper is the $ST$-diameter. Given two sets $S,T\subseteq V$, the $ST$-diameter is defined as $D_{S,T}≔{\max }_{s\in S,t\in T}d(s,t)$. Backurs, Roditty, Segal, Vassilevska W. and Wein explored this variant in [2]. We will use many of their results throughout this paper. We will use the following algorithms in approximating the undirected $k$-mode diameter.

Backurs et al. [2] also proved conditional lower bounds surrounding the hardness of approximating the $ST$-diameter.

In the following section we focus on $k$-multimode graphs with small values of $k$, $k\le \text{poly}\log (n)$. Under SETH and the Hitting Set Hypothesis, computing the exact $k$-mode diameter or radius requires $\mathrm{\Omega }({(nm)}^{1-o(1)})$ time, as it is at least as hard as computing these values in ordinary graphs [1]. Therefore, we have little hope of computing the exact diameter or radius polynomially faster than the trivial $\tilde{O}(mn)$ time algorithm. Instead, we focus on approximating these parameters.

In this work we focus on undirected graphs, for directed graphs refer to the full version. First, we present a simple algorithm running in linear time that provides a $3$-approximation to the $k$-mode diameter when $k=2$. We then show how to extend the idea of this algorithm to use in the context of a general $\alpha$-approximation. We use this extended idea to obtain a near $2$-approximation and a near $2.5$-approximation algorithm for $2$-mode diameter in the full version of this paper.

Next, we extend the $3$-approximation algorithm for $2$-mode diameter to the case of $k=3$ and obtain a near linear³³3Running in $\tilde{O}(m)$ time. time $3$-approximation algorithm for the $3$-mode diameter.

Finally, we turn our attention to approximating the $k$-mode radius of a $k$-multimode graph. Here we are able to show a $3$-approximation algorithm for the $k$-mode radius for any $k$, with a running time of $O(mk!)$.

In the full version we prove that for $k\ge 3$, any $3-\delta$ approximation algorithm for $k$-mode diameter must run in super linear time, showing that our near linear time $3$-approximation algorithm for $3$-mode diameter is in fact tight. Similarly, in the full version we also show that for $k\ge 3$, any $3-\delta$ approximation algorithm for $k$-mode radius must run in super linear time. Therefore, for any constant $k\ge 3$ our $3$-approximation algorithm for $k$-mode radius runs in near linear time and is tight.