2024/04/24 by Bansal, Shivam, Choudhary, Keerti, Dhanoa, Harkirat +1 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2404.16217
Given a directed graph G = (V, E) with n vertices, m edges and a designated source vertex s∈ 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 ⊆ E of at most k edges and any v∈ V, the (s, v)-max-flow in H ∖ F is equal to (s, v)-max-flow in G ∖ 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 λ2kn edges. 2. We also prove a matching lower bound of Ω(λ2kn) on the size of (λ,k)-FT-BFP. In particular, we show that for every λ,k,n≥ 1, there exists an n-vertex directed graph whose optimal (λ,k)-FT-BFP contains Ω(min\2kλn,n2\) 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)).