TY - GEN
T1 - Epic Fail
T2 - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023
AU - Bodwin, Greg
AU - Dinitz, Michael
AU - Nazari, Yasamin
PY - 2023/1/1
Y1 - 2023/1/1
N2 - A t-emulator of a graph G is a graph H that approximates its pairwise shortest path distances up to multiplicative t error. We study fault tolerant t-emulators, under the model recently introduced by Bodwin, Dinitz, and Nazari [ITCS 2022] for vertex failures. In this paper we consider the version for edge failures, and show that they exhibit surprisingly different behavior. In particular, our main result is that, for (2k − 1)-emulators with k odd, we can tolerate a polynomial number of edge faults for free. For example: for any n-node input graph, we construct a 5-emulator (k = 3) on O(n4/3) edges that is robust to f = O(n2/9) edge faults. It is well known that Ω(n4/3) edges are necessary even if the 5-emulator does not need to tolerate any faults. Thus we pay no extra cost in the size to gain this fault tolerance. We leave open the precise range of free fault tolerance for odd k, and whether a similar phenomenon can be proved for even k.
AB - A t-emulator of a graph G is a graph H that approximates its pairwise shortest path distances up to multiplicative t error. We study fault tolerant t-emulators, under the model recently introduced by Bodwin, Dinitz, and Nazari [ITCS 2022] for vertex failures. In this paper we consider the version for edge failures, and show that they exhibit surprisingly different behavior. In particular, our main result is that, for (2k − 1)-emulators with k odd, we can tolerate a polynomial number of edge faults for free. For example: for any n-node input graph, we construct a 5-emulator (k = 3) on O(n4/3) edges that is robust to f = O(n2/9) edge faults. It is well known that Ω(n4/3) edges are necessary even if the 5-emulator does not need to tolerate any faults. Thus we pay no extra cost in the size to gain this fault tolerance. We leave open the precise range of free fault tolerance for odd k, and whether a similar phenomenon can be proved for even k.
UR - http://www.scopus.com/inward/record.url?scp=85147552377&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2023.20
DO - 10.4230/LIPIcs.ITCS.2023.20
M3 - Conference contribution
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023
A2 - Kalai, Y.T.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 10 January 2023 through 13 January 2023
ER -