b'@online{Hu_2312.08489,'b"\nTITLE = {Connectivity Oracles for Predictable Vertex Failures},\nAUTHOR = {Hu, Bingbing and Kosinas, Evangelos and Polak, Adam},\nLANGUAGE = {eng},\nURL = {https://arxiv.org/abs/2312.08489},\nEPRINT = {2312.08489},\nEPRINTTYPE = {arXiv},\nYEAR = {2023},\nMARGINALMARK = {$\\bullet$},\nABSTRACT = {The problem of designing connectivity oracles supporting vertex failures is<br>one of the basic data structures problems for undirected graphs. It is already<br>well understood: previous works [Duan--Pettie STOC'10; Long--Saranurak FOCS'22]<br>achieve query time linear in the number of failed vertices, and it is<br>conditionally optimal as long as we require preprocessing time polynomial in<br>the size of the graph and update time polynomial in the number of failed<br>vertices.<br> We revisit this problem in the paradigm of algorithms with predictions: we<br>ask if the query time can be improved if the set of failed vertices can be<br>predicted beforehand up to a small number of errors. More specifically, we<br>design a data structure that, given a graph $G=(V,E)$ and a set of vertices<br>predicted to fail $\\widehat{D} \\subseteq V$ of size $d=|\\widehat{D}|$,<br>preprocesses it in time $\\tilde{O}(d|E|)$ and then can receive an update given<br>as the symmetric difference between the predicted and the actual set of failed<br>vertices $\\widehat{D} \\triangle D = (\\widehat{D} \\setminus D) \\cup (D \\setminus<br>\\widehat{D})$ of size $\\eta = |\\widehat{D} \\triangle D|$, process it in time<br>$\\tilde{O}(\\eta^4)$, and after that answer connectivity queries in $G \\setminus<br>D$ in time $O(\\eta)$. Viewed from another perspective, our data structure<br>provides an improvement over the state of the art for the \\emph{fully dynamic<br>subgraph connectivity problem} in the \\emph{sensitivity setting}<br>[Henzinger--Neumann ESA'16].<br> We argue that the preprocessing time and query time of our data structure are<br>conditionally optimal under standard fine-grained complexity assumptions.<br>},\n}\n"