Fault-Tolerant Bounded Flow Preservers

Abstract

Given a directed graph $G=(V,E)$ with $n$ vertices, $m$ edges and a designated source vertex $s\in V$, we consider the question of finding a sparse subgraph $H$ of $G$ that preserves the flow from $s$ up to a given threshold $\hat{I}»$ even after failure of $k$ edges. We refer to such subgraphs as $(\hat{I}»,k)$-fault-tolerant bounded-flow-preserver ($(\hat{I}»,k)$-FT-BFP). Formally, for any $F\subseteq E$ of at most $k$ edges and any $v\in V$, the $(s,v)$-max-flow in $H\setminus F$ is equal to $(s,v)$-max-flow in $G\setminus F$, if the latter is bounded by $\hat{I}»$, and at least $\hat{I}»$ otherwise. Our contributions are summarized as follows: 1. We provide a polynomial time algorithm that given any graph $G$ constructs a $(\hat{I}»,k)$-FT-BFP of $G$ with at most $\hat{I}»2^{k}n$ edges. 2. We also prove a matching lower bound of $\hat{I}\text{c◯}(\hat{I}»2^{k}n)$ on the size of $(\hat{I}»,k)$-FT-BFP. In particular, we show that for every $\hat{I}»,k,n\ge 1$, there exists an $n$-vertex directed graph whose optimal $(\hat{I}»,k)$-FT-BFP contains $\hat{I}\text{c◯}(\min \{2^k\hat{I}»n,n^2\})$ edges. 3. Furthermore, we show that the problem of computing approximate $(\hat{I}»,k)$-FT-BFP is NP-hard for any approximation ratio that is better than $O(\log (\hat{I}{»}^{-1}n))$.

12 pages, 2 figures