Testing whether a subgraph is convex or isometric

We consider the following two algorithmic problems: given a graph G and a subgraph H⊆ G, decide whether H is an isometric or a geodesically convex subgraph of G. It is relatively easy to see that the problems can be solved by computing the distances between all pairs of vertices. We provide a conditional lower bound showing that, for sparse graphs with n vertices and $Θ(n)$ edges, we cannot expect to solve the problem in O(n2-ε) time for any constant ε>0. We also show that the problem can be solved in subquadratic time for planar graphs and in near-linear time for graphs of bounded treewidth. Finally, we provide a near-linear time algorithm for the setting where G is a plane graph and H is defined by a few cycles in G.