New Lower Bounds and Upper Bounds for Listing Avoidable Vertices

We consider the problem of listing all avoidable vertices in a given n vertex graph. A vertex is avoidable if every pair of its neighbors is connected by a path whose internal vertices are not neighbors of the vertex or the vertex itself. Recently, Papadopolous and Zisis showed that one can list all avoidable vertices in O(n^{ω+1}) time, where ω < 2. 373 is the square matrix multiplication exponent, and conjectured that a faster algorithm is not possible. In this paper we show that under the 3-OV Hypothesis, and thus the Strong Exponential Time Hypothesis, n^{3-o(1)} time is needed to list all avoidable vertices, and thus the current best algorithm is conditionally optimal if ω = 2. We then show that if ω > 2, one can obtain an improved algorithm that for the current value of ω runs in O(n^3. 32) time. We also show that our conditional lower bound is actually higher and supercubic, under a natural High Dimensional 3-OV hypothesis, implying that for our current knowledge of rectangular matrix multiplication, the avoidable vertex listing problem likely requires Ω(n^3. 25) time. We obtain further algorithmic improvements for sparse graphs and bounded degree graphs.

Authors

• Mingyang Deng
• Virginia Vassilevska Williams
• Ziqian Zhong

Keywords

• Avoidable Vertex
• Fine-Grained Complexity