Testing whether a subgraph is convex or isometric
For graph theorists and algorithm designers, the paper establishes hardness and provides efficient algorithms for fundamental graph properties, though the results are incremental.
The paper studies the problems of testing whether a subgraph is isometric or geodesically convex in a graph, providing a conditional lower bound showing that for sparse graphs with n vertices and Θ(n) edges, the problem cannot be solved in O(n^{2-ε}) time. It also gives subquadratic algorithms for planar graphs and near-linear algorithms for graphs of bounded treewidth and for plane graphs where H is defined by a few cycles.
We consider the following two algorithmic problems: given a graph $G$ and a subgraph $H\subseteq 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(n^{2-\varepsilon})$ time for any constant $\varepsilon>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$.