Sparse weight tolerant subgraph for single source shortest path

DOI10.4230/LIPICS.SWAT.2018.15zbMATH Open1477.05177arXiv1707.04867OpenAlexW2805276497MaRDI QIDQ5116479FDOQ5116479

Diptarka Chakraborty, Debarati Das

Publication date: 25 August 2020

Abstract: In this paper we address the problem of computing a sparse subgraph of a weighted directed graph such that the exact distances from a designated source vertex to all other vertices are preserved under bounded weight increment. Finding a small sized subgraph that preserves distances between any pair of vertices is a well studied problem. Since in the real world any network is prone to failures, it is natural to study the fault tolerant version of the above problem. Unfortunately, it turns out that there may not always exist such a sparse subgraph even under single edge failure [Demetrescu emph{et al.} '08]. However in real applications it is not always the case that a link (edge) in a network becomes completely faulty. Instead, it can happen that some links become more congested which can easily be captured by increasing weight on the corresponding edges. Thus it makes sense to try to construct a sparse distance preserving subgraph under the above weight increment model. To the best of our knowledge this problem has not been studied so far. In this paper we show that given any weighted directed graph with $n$ vertices and a source vertex, one can construct a subgraph that contains at most $ecdot(k-1)!2^{k}n$ many edges such that it preserves distances between the source and all other vertices as long as the total weight increment is bounded by $k$ and we are allowed to have only integer valued (can be negative) weight on each edge and also weight of an edge can only be increased by some positive integer. Next we show a lower bound of $ccdot{2}^{k}n$, for some constant $cge5/4$, on the size of the subgraph. We also argue that restriction of integer valued weight and integer valued weight increment are actually essential by showing that if we remove any one of these two restrictions we may need to store $Omega(n^2)$ edges to preserve distances.

Full work available at URL: https://arxiv.org/abs/1707.04867

Recommendations

• scientific article; zbMATH DE number 6850433
• Preserving distances in very faulty graphs
• Fault tolerant subgraph for single source reachability: generic and optimal
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Fault-tolerant spanners for general graphs

zbMATH Keywords

fault tolerantgraph algorithmshortest pathdistance preserver

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Paths and cycles (05C38)

Cites Work

• An Incremental Algorithm for a Generalization of the Shortest-Path Problem
• Oracles for Distances Avoiding a Failed Node or Link
• A nearly optimal oracle for avoiding failed vertices and edges
• A fast algorithm for finding dominators in a flowgraph
• Fault-tolerant spanners
• Title not available (Why is that?)
• Speeding up dynamic shortest-path algorithms
• Title not available (Why is that?)
• Fault tolerant additive and \((\mu, \alpha)\)-spanners
• Dual failure resilient BFS structure
• Sparse Fault-Tolerant BFS Trees
• Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication
• Improved Purely Additive Fault-Tolerant Spanners
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multiple Source Dual Fault Tolerant BFS Trees
• Fault tolerant subgraph for single source reachability: generic and optimal
• Vertex fault tolerant additive spanners
• Title not available (Why is that?)
• New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners
• Fault-tolerant geometric spanners
• Fault-Tolerant Approximate Shortest-Path Trees
• Replacement paths and k simple shortest paths in unweighted directed graphs
• A Hierarchy of Lower Bounds for Sublinear Additive Spanners
• Fault-tolerant spanners for general graphs
• Additive Spanners in Nearly Quadratic Time
• The 4/3 additive spanner exponent is tight
• Title not available (Why is that?)
• Fault Tolerant Approximate BFS Structures
• Title not available (Why is that?)

This page was built for publication: Sparse weight tolerant subgraph for single source shortest path

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116479)