2026-08-07T18:21:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16839 2024-03-06T10:58:28Z ddc:004 open_access

New Lower Bounds and Upper Bounds for Listing Avoidable Vertices Deng, Mingyang Vassilevska Williams, Virginia Zhong, Ziqian Avoidable Vertex Fine-Grained Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mingyang Deng and Virginia Vassilevska Williams and Ziqian Zhong 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.41 urn:nbn:de:0030-drops-168392 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.41 eng https://creativecommons.org/licenses/by/4.0/legalcode