Deng, Mingyang ;
Vassilevska Williams, Virginia ;
Zhong, Ziqian
New Lower Bounds and Upper Bounds for Listing Avoidable Vertices
Abstract
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 3OV Hypothesis, and thus the Strong Exponential Time Hypothesis, n^{3o(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 3OV 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.
BibTeX  Entry
@InProceedings{deng_et_al:LIPIcs.MFCS.2022.41,
author = {Deng, Mingyang and Vassilevska Williams, Virginia and Zhong, Ziqian},
title = {{New Lower Bounds and Upper Bounds for Listing Avoidable Vertices}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {41:141:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772563},
ISSN = {18688969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16839},
URN = {urn:nbn:de:0030drops168392},
doi = {10.4230/LIPIcs.MFCS.2022.41},
annote = {Keywords: Avoidable Vertex, FineGrained Complexity}
}
22.08.2022
Keywords: 

Avoidable Vertex, FineGrained Complexity 
Seminar: 

47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Issue date: 

2022 
Date of publication: 

22.08.2022 