08 May 2025 – Martin Schirneck

Date: 08 May 2025
Time: 11:45 – 12:45
Location: Forschungslabor 3 (sofa room)

Speaker: Martin Schirneck
Title: Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks

Abstract:
This talk is about the design of fault-tolerant data structures that can report graph parameters like distances or connectivity even after some edges of the underlying graph G have failed. An important tool in the area are (L,f)-replacement path coverings (RPCs). These are families of subgraphs of G that guarantee the following property for every set F of at most f edge failures and every pair of vertices s and t: If there is a shortest s-t-path in the graph G-F that has at most L edges, then at least one subgraph in the RPC contains no edge of F but all edges of this replacement path. We present a new construction of (L,f)-replacement path coverings whose parameters improve over previous works by Weimann and Yuster [FOCS 2010] as well as Karthik and Parter [SODA 2021]. We then briefly discuss how this can be used to construct fault-tolerant data structures for shortest paths and even for NP-hard problems like k-Path and k-Clique.

The talk is based on joined work with Davide Bilò, Keerti Choudhary, Sarel Cohen, and Tobias Friedrich that appeared at AAAI 2025.