Fault-Tolerant Bounded Flow Preservers

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 $λ$ even after failure of $k$ edges. We refer to such subgraphs as $(λ,k)$-fault-tolerant bounded-flow-preserver ($(λ,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 $λ$, and at least $λ$ otherwise. Our contributions are summarized as follows: 1. We provide a polynomial time algorithm that given any graph $G$ constructs a $(λ,k)$-FT-BFP of $G$ with at most $λ2^kn$ edges. 2. We also prove a matching lower bound of $Ω(λ2^kn)$ on the size of $(λ,k)$-FT-BFP. In particular, we show that for every $λ,k,n\geq 1$, there exists an $n$-vertex directed graph whose optimal $(λ,k)$-FT-BFP contains $Ω(\min\{2^kλn,n^2\})$ edges. 3. Furthermore, we show that the problem of computing approximate $(λ,k)$-FT-BFP is NP-hard for any approximation ratio that is better than $O(\log(λ^{-1} n))$.