TY - GEN
T1 - Sparse weight tolerant subgraph for single source shortest path
AU - Chakraborty, Diptarka
AU - Das, Debarati
N1 - Funding Information:
Funding The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013)/ERC Grant Agreement no. 616787.
Publisher Copyright:
© Diptarka Chakraborty and Debarati Das.
PY - 2018/6/1
Y1 - 2018/6/1
N2 - In this paper we address the problem of computing a sparse subgraph of any 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 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 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 where total increase in weight in the whole network (graph) is bounded by some parameter k. 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 of size at most e·(k−1)!2kn 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 only have integer valued (can be negative) weight on edges and also weight of an edge can only be increased by some positive integer. Next we show a lower bound of c·2kn, for some constant c ≥ 5/4, on the size of such a subgraph. We further argue that the restrictions of integral weight and integral weight increment are actually essential by showing that if we remove any one of these two we may need to store (n2) edges to preserve the distances.
AB - In this paper we address the problem of computing a sparse subgraph of any 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 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 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 where total increase in weight in the whole network (graph) is bounded by some parameter k. 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 of size at most e·(k−1)!2kn 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 only have integer valued (can be negative) weight on edges and also weight of an edge can only be increased by some positive integer. Next we show a lower bound of c·2kn, for some constant c ≥ 5/4, on the size of such a subgraph. We further argue that the restrictions of integral weight and integral weight increment are actually essential by showing that if we remove any one of these two we may need to store (n2) edges to preserve the distances.
UR - http://www.scopus.com/inward/record.url?scp=85049027946&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85049027946&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SWAT.2018.15
DO - 10.4230/LIPIcs.SWAT.2018.15
M3 - Conference contribution
AN - SCOPUS:85049027946
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 151
EP - 1515
BT - 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018
A2 - Eppstein, David
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018
Y2 - 18 June 2018 through 20 June 2018
ER -