Testing Whether a Subgraph Is Convex or Isometric

Let $G$ be an undirected graph with abstract, positive edge lengths $\mathrm{\ell }:E(G)\to {ℝ}_{>0}$. We call $G$ the host graph and assume henceforth that it is connected. The length of a walk (or path) $\pi$ in $G$, denoted by $\mathrm{\ell }(\pi )$, is the sum of the lengths of its edges; thus $\mathrm{\ell }(\pi )={\sum }_{e\in E(\pi )}\mathrm{\ell }(e)$, where the sum is with multiplicity. For any two vertices $x,y\in V(G)$, a shortest path from $x$ to $y$ is a minimum-length path connecting $x$ and $y$, and the distance between $x$ and $y$ in $G$, denoted by $d_G(x,y)$, is the length of a shortest path from $x$ to $y$.

For any two vertices $x,y$ of $G$, the interval $I_G(x,y)$ is the subgraph of $G$ defined by the union of all shortest paths from $x$ to $y$. Formally

A subgraph $H$ of $G$ is (geodesically) convex (in $G$) if and only if

and it is isometric (in $G$) if and only if

We consider the following algorithmic problems:

• $\mathrm{■}$

  Given a host graph $G$ and a subgraph $H\subseteq G$, decide whether $H$ is an isometric subgraph.

• $\mathrm{■}$

  Given a host graph $G$ and a subgraph $H\subseteq G$, decide whether $H$ is a convex subgraph.

In graph theory, the concepts of isometric and (geodesically) convex subgraphs are defined for the setting where $\mathrm{\ell }(e)=1$ for all $e\in E(G)$. In this unit-length setting, only induced subgraphs are considered because non-induced graphs cannot be isometric nor convex. In the general case with edge lengths, we may have for some edges $xy$ of $G$.

Henceforth, we use $n$ and $m$ for the number of vertices and edges of the host graph $G$.

Dourado et al. [16] provide an efficient algorithm to test convexity in the case of unit-length edges. Their approach can be easily adapted to graphs with arbitrary edge lengths, as follows. For each vertex $x$ of the subgraph $H$, one computes the graph $H_x={\bigcup }_{y\in V(H)}{I}_G(x,y)$. The subgraph $H$ is convex in $G$ if and only if $H_x$ is contained in $H$ for all $x\in V(H)$. The computation of $H_x$ takes $O(m)$ time once we have a shortest-path tree in $G$ from $x$, and testing whether $H_x\subseteq H$ also takes $O(m)$ time.

We conclude that testing whether a subgraph is convex can be done by computing a shortest-path tree from each vertex, the co-called all-pairs shortest-path (APSP) problem, followed by tests that take $O(nm)$ time. With a simple modification, the same time bound holds for testing whether the given subgraph is isometric. The running time to solve the APSP problem depends on the assumptions about the edge lengths:

• $\mathrm{■}$

  for unit edge lengths, the APSP problem is solved in $O(nm)$ using a simple BFS;

• $\mathrm{■}$

  when the edge lengths are natural numbers and multiplications take constant time, Thorup [46] solves the APSP problem in $O(nm)$ time;

• $\mathrm{■}$

  if we only perform additions and comparisons of edge lengths, then the algorithm of Pettie and Ramachandran [40] for APSP takes $O(nm\alpha (m,n))$ time. Using Dijkstra’s algorithm with Fibonacci heaps [20], the running time is slightly worse, $O(n^2\log n+nm)$.

We conclude that testing whether a subgraph is convex or isometric can be done in $\tilde{O}(nm)$ time in all situations.

Convex subgraphs play an important role in the theory of median graphs [12, 35, 36, 37], a class of graphs that has received substantial attention [3, 24, 31]. For median graphs, convex sets and so-called gated sets are the same concept; see for example [4, Lemma 3.3]. This can be used to test convexity in linear time: it suffices to check whether every vertex outside $H$ has at most one neighbor in $H$. Imrich and Klavžar [27] provided a characterization of convex subgraphs in bipartite graphs in terms of $\mathrm{\Theta }$-classes. The characterization is for unit edge lengths and leads to an algorithm taking $O(nm)$ time. They used it to obtain a fast algorithm to recognize median graphs. See also [23]. It was later shown that the recognition of median graphs is closely related to the detection of triangles in graphs [28]. If the host graph $G$ is the Cartesian product of graphs, $G=G_1\mathrm{\square }\mathrm{\dots }\mathrm{\square }{G}_k$, and the edges have unit length, a subgraph $H\subseteq G$ is convex if and only if $H=H_1\mathrm{\square }\mathrm{\dots }\mathrm{\square }{H}_k$, where each $H_i$ is a convex subgraph of $G_i$; see [24, Lemma 6.5]. Together with linear-time algorithms for factorization of graphs [29], this leads to an efficient algorithm for Cartesian products of substantially smaller graphs. Convex subgraphs are being considered also in more applied areas; see for example [21, 34, 44, 45].

A graph is a partial cube [15, 19, 48] if it is isomorphic to an isometric subgraph of some hypercube $Q_d$. Partial cubes enjoy a rich structure and appear in several different combinatorial settings; see for example [3, 24, 38]. Eppstein [18] provided an algorithm to test in $O(n^2)$ time whether a given graph with $n$ vertices is a partial cube. Note that this setting is different to ours because we are not given a subgraph of $Q_d$, but have to test whether a given graph is isomorphic to an isometric subgraph of $Q_d$. In our setting, we are given a subgraph. The concept of isometric embeddings in the hypercube or other products of graphs has also been studied recently for weighted graphs; see [5, 42].

We first provide a series of characterizations of isometric (Section 2) and convex subgraphs (Section 3). Most notably, one of the characterizations uses a marked version of the of the so-called Wiener index, which we will define below. We think that the characterizations are new and of independent interest. Although proving each of our characterizations is not difficult, identifying them is closely related to the development of our algorithms.

Our first result regarding algorithms is the following conditional lower bound: if $G$ has $n$ vertices and $\mathrm{\Theta }(n)$ edges, then there is no algorithm to test whether a given subgraph $H$ of $G$ is isometric or convex in $O(n^{2-\epsilon })$ time, for any constant $\epsilon >0$, unless the Orthogonal Vectors Conjecture (OVC) and the Strong Exponential Time Hypothesis (SETH) fail. This means that for general graphs we cannot expect to test whether a subgraph is convex or isometric in, say, $O(n{m}^{0.999})$ time, unless some standard assumptions are wrong. The lower bound holds for graphs with unit edge lengths and implies that the algorithms mentioned above, with running times $\tilde{O}(nm)$, are asymptotically optimal up to polynomial factors $\mathrm{\Theta }(n^{\epsilon })$ for any $\epsilon >0$. Our reduction is via the diameter problem. We review OVC and SETH in Section 4, where we also provide our reduction via the diameter problem.

The characterization using the marked version of the Wiener index can be combined with adaptations of known algorithms to obtain the following results about testing whether a given subgraph is isometric or convex:

• $\mathrm{■}$

  If the host graph is planar graph, the test can be performed in $\tilde{O}(n^{5/3})$ time.

• $\mathrm{■}$

  If the host graph has treewidth bounded by a constant $k\ge 3$, the test can be performed in $O(n{\log }^{k-1}n)$ time; the constant in the $O$-notation depends on $k$. When the treewidth $k$ is considered a parameter, the test can be performed in $n^{1+\epsilon }{2}^{O(k)}$, for any constant $\epsilon >0$; the constant in the $O$-notation depends on the choice of $\epsilon$.

Finally, in Section 6 we consider the following setting. The host graph $G$ is a plane graph, that is, a planar graph with a fixed embedding in the plane. Let $C$ be a cycle in $G$ and let $H=\mathrm{int}(G,C)$ be the subgraph of $G$ bounded by $C$ and including $C$; see Figure 1 left. We show how to decide whether $H$ is an isometric or a convex subgraph of $G$ in $O(n\log n)$ time. The result can be extended to subgraphs of $G$ defined by a constant number of cycles; see the right of Figure 1 for an example and Section 6 for more precise definitions. Compared to the other results presented in the paper, this result is interesting because it uses different characterizations and a different algorithmic paradigm. We use multiple-source shortest-path (MSSP) algorithms for planar graphs [9, 32] and combine the distances in the interior and the exterior of $C$, as the source of the shortest-path tree moves along the cycle $C$. As far as we know, this is the first application of MSSP where we maintain a combination of the interior and the exterior distances.

Through our discussion we will assume that the host graph $G$ is fixed and in the notation we will often drop the dependency on $G$.

For each subgraph $H$ of $G$, the boundary of $H$ (in $G$) is the set $\partial H$ of vertices of $H$ that are incident to some edge outside $H$. Thus, $\partial H=\{v\in V(H)\mid \exists uv\in E(G)\setminus E(H)\}$. Note that each path in $G$ that has edges from $E(H)$ and edges from $E(G)\setminus E(H)$ must have some vertex of $\partial H$.

For each subgraph $H$ of $G$, let $H_{\mathrm{out}}$ be the complement of $H$ in $G$, defined as the subgraph with edges not contained in $H$. Thus, $H_{\mathrm{out}}=(V(G),E(G)\setminus E(H))$. The graph $H_{\mathrm{out}}$ may have isolated vertices. For distances in $H_{\mathrm{out}}$ we write $d_{H_{\mathrm{out}}}(\cdot ,\cdot )$.

We will often use without explicit mention that for any subgraph $H$ of $G$ and any vertices $x,y\in V(H)$ we have $d_G(x,y)\le d_H(x,y)$ and $d_G(x,y)\le d_{H_{\mathrm{out}}}(x,y)$.

The Wiener index with marked vertices for a graph $G$ with respect to $U\subseteq V(G)$ is ${\sum }_{x,y\in U}{d}_G(x,y)$. The classical Wiener index is the case of $U=V(G)$. For unweighted graphs, this is a very similar to the vertex-weighted medians considered by Bandelt and Chepoi [2] and it is a particular case of the vertex-weighted Wiener index considered by Bénéteau et al. [4] for median graphs. In their weighted version, the marked vertices have weight $1$ and the vertices to be ignored in the sum have weight $0$.

Assume first that $H$ is a convex subgraph of $G$. Consider any two vertices $x,y$ of $H$ and let ${\pi }_{x,y}$ be a shortest path in $G$ from $x$ to $y$ with respect to $\widehat{\mathrm{\ell }}$. Therefore ${\widehat{d}}_G(x,y)=\widehat{\mathrm{\ell }}({\pi }_{x,y})$. Because of Section 3, the path ${\pi }_{x,y}$ is a shortest path in $G$ with respect to $\mathrm{\ell }$, which means that $\mathrm{\ell }({\pi }_{x,y})=d_G(x,y)$. Because $H$ is convex, the path ${\pi }_{x,y}$ is contained in $H$, and since the edges of $H$ have the same length in $\mathrm{\ell }$ and in $\widehat{\mathrm{\ell }}$, we have $\widehat{\mathrm{\ell }}({\pi }_{x,y})=\mathrm{\ell }({\pi }_{x,y})$. Putting the forthcoming equalities together and using that $H$ is a convex (and thus isometric) subgraph of $G$, we obtain

Since this equality holds for each $x,y\in V(H)$, we obtain

To show the other direction, note first that ${\widehat{d}}_G(x,y)\le d_G(x,y)\le d_H(x,y)$ for all $x,y\in V(H)$ because $\widehat{\mathrm{\ell }}(e)\le \mathrm{\ell }(e)$ for all edges $e\in E(G)$ (for the first inequality) and $H$ is a subgraph of $G$ (for the second inequality). Assume now that $H$ is not a convex subgraph of $G$. This means that there exists vertices $x_0,y_0\in V(H)$ and a $x_0$-to-$y_0$ shortest path ${\pi }_0$ that is not contained in $H$. Since ${\pi }_0$ has some edge in $E(G)\setminus E(H)$, we have and therefore . Therefore

$◀$

In the first part of the proof of Section 3 we have seen that, if $H$ is a convex subgraph of $G$, then for all $x,y\in V(H)$ we have ${\widehat{d}}_G(x,y)=d_H(x,y)$. The equality of the two sums follows.

For the other direction, we start assuming that $H$ is not a convex subgraph of $G$. If $H$ is not connected, then the left sum is $\mathrm{\infty }$ while the right side is bounded, and therefore they are distinct. We continue assuming that $H$ is connected. By Section 3, there exist distinct vertices $x_0,y_0\in \partial H$ such that $d_H(x_0,y_0)\ge d_{H_{\mathrm{out}}}(x_0,y_0)$. Let ${\pi }_0$ be a shortest $x_0$-to-$y_0$ path in $H$ and let ${\pi }_0^{\prime }$ be a shortest $x_0$-to-$y_0$ path in $H_{\mathrm{out}}$. Note that ${\pi }_0^{\prime }$ indeed exists because $d_{H_{\mathrm{out}}}(x_0,y_0)$ is bounded. We then have $\mathrm{\ell }({\pi }_0)=d_H(x_0,y_0)\ge d_{H_{\mathrm{out}}}(x_0,y_0)=\mathrm{\ell }({\pi }_0^{\prime })$. Since ${\pi }_0^{\prime }$ has edges outside $E(H)$, we have , and therefore

In summary, for some $x_0,y_0\in \partial H$. In general, for all $x,y\in V(H)$ we have ${\widehat{d}}_G(x,y)\le d_G(x,y)\le d_H(x,y)$ because $\widehat{\mathrm{\ell }}(e)\le \mathrm{\ell }(e)$ for all edges $e\in E(G)$ (for the first inequality) and $H$ is a subgraph of $G$ (for the second inequality). From this it follows that for $U$ such that $\partial H\subseteq U\subseteq V(H)$ we have

$◀$

We will reduce from the diameter problem considered in Theorem 8. Let $H$ be a graph with $O(n)$ vertices and $O(n)$ edges, all edges of unit length, for which we want to distinguish whether it has diameter $2$ or $3$. Consider the graph $G=G(H)$ defined as follows; see Figure 2 for an example. We first construct the graph $H_3$ from $H$ by subdividing each edge of $H$ twice. Then, we add a new vertex $v_{\ast }$ and connect it to each vertex of $V(H)$ with a $4$-edge path using new interior vertices. Let $G=G(H)$ be the resulting graph. Note that $H_3$ is a subgraph of $G$ and $\partial H_3=V(H)$.

We assign unit length to each edge of $G$. For all $x,y\in V(H)$, we have $d_{H_3}(x,y)=3\cdot d_H(x,y)$ and $d_G(x,y)=\min \{3\cdot d_H(x,y),8\}$, where the $8$ comes from the path in $G$ through $v_{\ast }$.

We now show that $H_3$ is an isometric subgraph of $G$ if and only if $H$ has diameter $2$. If $H$ has diameter $2$, then for all $x,y\in V(H)$ we have

Since $\partial H_3=V(H)$, we have ${\sum }_{x,y\in \partial H_3}{d}_G(x,y)={\sum }_{x,y\in \partial H_3}{d}_{H_3}(x,y)$ and $H_3$ is an isometric subgraph of $G$ because of Section 2. If $H$ has diameter $3$, then there is some $x_0,y_0\in V(H)$ with $d_H(x_0,y_0)=3$, and therefore $d_{H_3}(x_0,y_0)=3\cdot d_H(x_0,y_0)=9>8\ge d_G(x_0,y_0)$. It follows that $H_3$ is not an isometric subgraph of $G$.

We now show that $H_3$ is a convex subgraph of $G$ if and only if $H$ has diameter $2$. Let $\widehat{d}$ denote the distance in $G$ when we decrease the length of the edges of $E(G)\setminus E(H_3)$ by a sufficiently small value $\delta >0$. For concreteness, we can take in our discussion. Then, for all $x,y\in V(H)$, we have $d_{H_3}(x,y)=3\cdot d_H(x,y)$ and ${\widehat{d}}_G(x,y)=\min \{3\cdot d_H(x,y),8-8\delta \}$.

If $H$ has diameter $2$, then, for all $x,y\in V(H)$, we have

where we have used that $3\cdot d_H(x,y)\le 6$ and . Since $\partial H_3=V(H)$, we have ${\sum }_{x,y\in \partial H_3}{\widehat{d}}_G(x,y)={\sum }_{x,y\in \partial H_3}{d}_{H_3}(x,y)$, and $H_3$ is a convex subgraph of $G$ because of Section 3.

If $H$ has diameter $3$, then we have already seen that $H_3$ is not an isometric subgraph of $G$, and thus cannot be a convex subgraph.

If $H$ has $O(n)$ vertices and $O(n)$ edges, then $G$ has $|V(H)|+2\cdot |E(H)|+3\cdot |V(H)|+1=O(n)$ vertices and $3\cdot |E(H)|+4\cdot |V(H)|=O(n)$ edges. The construction of $G$ and $H_3$ from $H$ takes linear time. It follows that, if we could decide whether $H_3$ is isometric (or convex) in $O(n^{2-\epsilon })$ time, for some $\epsilon >0$, we could decide whether $H$ has diameter $2$ or $3$ in $O(n^{2-\epsilon })$ time, and therefore OVC and SETH would be false by Theorem 8. $◀$