DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2024.9

Fault-Tolerant Bounded Flow Preservers

Authors: Shivam Bansal, Keerti Choudhary, Harkirat Dhanoa, and Harsh Wardhan

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract

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 λ 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 ⩾ 1, there exists an n-vertex directed graph whose optimal (λ,k)-FT-BFP contains Ω(min{2^kλ n, n²}) 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)).

Cite as

Shivam Bansal, Keerti Choudhary, Harkirat Dhanoa, and Harsh Wardhan. Fault-Tolerant Bounded Flow Preservers. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bansal_et_al:LIPIcs.ISAAC.2024.9,
  author =	{Bansal, Shivam and Choudhary, Keerti and Dhanoa, Harkirat and Wardhan, Harsh},
  title =	{{Fault-Tolerant Bounded Flow Preservers}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.9},
  URN =		{urn:nbn:de:0030-drops-221363},
  doi =		{10.4230/LIPIcs.ISAAC.2024.9},
  annote =	{Keywords: Fault-tolerant Data-structures, Max-flow, Bounded Flow Preservers}
}

Search Results

Documents authored by Dhanoa, Harkirat

Fault-Tolerant Bounded Flow Preservers

Abstract

Cite as

Thanks for your feedback!

Could not send message