Vertex fault tolerant additive spanners

A fault-tolerant structure for a network is required to continue functioning following the failure of some of the network’s edges or vertices. In this paper, we address the problem of designing a fault-tolerant additive spanner, namely, a subgraph H of the network G such that subsequent to the failure of a single vertex, the surviving part of H still contains an additive spanner for (the surviving part of) G, satisfying dist(s,t,H\{v})≤dist(s,t,G\{v})+β\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm{dist}(s,t,H{\setminus } \{v\}) \le \mathrm{dist}(s,t,G{\setminus } \{v\})+\beta $$\end{document} for every s,t,v∈V\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s,t,v \in V$$\end{document}. Recently, the problem of constructing fault-tolerant additive spanners resilient to the failure of up to fedges has been considered (Braunschvig et al. Proceedings of the WG, pp 206–214, 2012). The problem of handling vertex failures was left open therein. In this paper we develop new techniques for constructing additive FT-spanners overcoming the failure of a single vertex in the graph. Our first result is an FT-spanner with additive stretch 2 and O(n5/3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^{5/3})$$\end{document} edges. Our second result is an FT-spanner with additive stretch 6 and O(n3/2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^{3/2})$$\end{document} edges. The construction algorithm consists of two main components: (a) constructing an FT-clustering graph and (b) applying a modified path-buying procedure suitably adapted to failure prone settings. Finally, we also describe two constructions for fault-tolerant multi-source additive spanners, aiming to guarantee a bounded additive stretch following a vertex failure, for every pair of vertices in S×V\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S \times V$$\end{document} for a given subset of sources S⊆V\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S\subseteq V$$\end{document}. The additive stretch bounds of our constructions are 4 and 8 (using a different number of edges).