2026-07-24T01:08:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22849 2025-10-02T13:35:26Z ddc:004 open_access

A Deterministic Approach to Shortest Path Restoration in Edge Faulty Graphs Choudhary, Keerti Dhiman, Rishabh Fault-tolerant Data-structures Shortest Path Restoration Replacement path Afek, Bremler-Barr, Kaplan, Cohen, and Merritt (PODC'01) in their seminal work on shortest path restorations demonstrated that after a single edge failure in a graph G, a replacement shortest path between any two vertices s and t, which avoids the failed edge, can be represented as the concatenation of two original shortest paths in G. They also showed that we cannot associate a canonical shortest path between the vertex pairs in G that consistently allows for the replacement path (in the surviving graph) to be represented as a concatenation of these canonical paths. Recently, Bodwin and Parter (PODC'21) proposed a randomized tie-breaking scheme for selecting canonical paths for the "ordered" vertex pairs in graph G with the desired property of representing the replacement shortest path as a concatenation of canonical shortest-paths provided for ordered pairs. An interesting open question is whether it is possible to provide a deterministic construction of canonical paths in an efficient manner. We address this question in our paper by presenting an O(mn) time deterministic algorithm to compute a canonical path family ℱ = {P_{x,y}, Q_{x,y} | x,y ∈ V} comprising of two paths per (unordered) vertex pair. Each replacement is either a PQ-path (of type P_{x,y}∘Q_{y,z}), a QP-path, a QQ-path, or a PP-path. Our construction is fairly simple and is a straightforward application of independent spanning trees. We also present various applications of family ℱ in computing fault-tolerant structures. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Keerti Choudhary and Rishabh Dhiman 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.24 urn:nbn:de:0030-drops-228499 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.24 eng https://creativecommons.org/licenses/by/4.0/legalcode