Low-Cost Arborescence Under Edge Faults

2026

Read Low-Cost Arborescence Under Edge Faults (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13800.txt.

Introduction

Dipan Dey and Telikepalli Kavitha study low-cost arborescence under edge faults in a directed graph with a designated root and non-negative edge costs. Edge faults are transient: when one edge fails, the min-cost arborescence must be updated for the graph minus that edge. Computing a fresh min-cost arborescence takes O(m plus n log n) time, so the authors seek a sparse subgraph H built in preprocessing. They give a simple polynomial-time algorithm building H of size O(n to the 3 halves).

Catalog record

YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50725
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.13800

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Low-Cost Arborescence Under Edge Faults Abstract Low-Cost Arborescence Under Edge Faults Dipan Dey University of Houston Houston, USA [email protected] Telikepalli Kavitha Tata Institute of Fundamental Research Mumbai, India [email protected] Abstract Our input is a directed graph G=(V,E) on n vertices and m edges with a designated root vertex r and a function \mathsf{cost}:E\rightarrow\mathbb{R}_{\geq 0} . The problem is to maintain a min-cost arborescence in G in the presence of edge faults (a single fault at a time). Edge faults are transient and once the faulty edge is repaired, the original min-cost arborescence \mathcal{T} is restored. Whenever an edge fault happens, we need to update \mathcal{T} to a min-cost arborescence in G-f , where f is the faulty edge. Since computing a min-cost arborescence in G-f takes O(m+n\log n) time, we seek to construct a sparse subgraph H in a preprocessing step such that in the event of any edge f failing, it suffices to compute a min-cost arborescence in H-f in order to find a low-cost arborescence in G-f . In the unweighted setting (i.e., \mathsf{cost}(e)=1 for all e\in E ), this is the fault-tolerant subgraph problem for single-source reachability . Baswana, Choudhary, and Roditty (SICOMP, 2018) showed a k -fault tolerant reachability subgraph of size O(2^{k}n) , where k is the number of edge faults; moreover, this bound is tight. To the best of our knowledge, this problem has not been addressed in the weighted setting, i.e., when edges have costs. We show a simple polynomial-time algorithm to construct a subgraph H of size O(n^{3/2}) such that, for any f\in E , a min-cost arborescence in H-f is a 2-approximation of a min-cost arborescence in G-f . Thus whenever an edge fault happens, we can find a 2-approximate min-cost arborescence in G-f in O(n^{3/2}) time. Our second problem is in the matroid setting. The input is a matroid M=(E,{\cal I}) with a function \mathsf{cost}:E\rightarrow\mathbb{R} . The problem is to compute a sparse S\subseteq E (called a k -fault tolerant preserver) such that for any F\subseteq E with |F|\leq k , the matroid M|(S\setminus F) (restriction of M to S\setminus F ) contains a min-cost basis of M|(E\setminus F) . So when F is the set of failed elements, it suffices to compute a min-cost basis in M|(S\setminus F) rather than in M|(E\setminus F) . We show a tight bound of k\!\cdot\!\mathsf{rank}(E) on the size of a k -fault tolerant preserver, where \mathsf{rank}:2^{E}\rightarrow\mathbb{Z}_{\geq 0} is the rank function of M . 1 Introduction Our input is a directed graph G=(V,E) with a designated root vertex r , where the vertex r has no incoming edge. An arborescence in G is an acyclic subgraph in which each vertex, except one called the root, has a unique incoming edge. Since r has no incoming edge, observe that all arborescences in G have to be rooted at r . Thus every vertex is reachable from r in an arborescence. There is a function \mathsf{cost}:E\rightarrow\mathbb{R}_{\geq 0} and the problem is to compute a min-cost arborescence in G . This is a classic problem in graph algorithms [ 7 , 9 , 14 ] and the algorithm of Gabow, Galil, Spencer, and Tarjan [ 15 ] finds one in O(m+n\log n) time where |E|=m and |V|=n . As is well-known with real-world networks, links are prone to failures. It is unlikely that several links fail simultaneously, so we consider the case of a single edge failure. Thus the setting is as follows: we have computed a min-cost arborescence \mathcal{T} in G and an edge f\in E has failed. If f\in\mathcal{T} then we need to find a new min-cost arborescence \mathcal{T}_{f} in G-f . 1 1 1 For convenience, we use G-f to denote the subgraph (V,E\setminus\{f\}) of G . We assume any edge fault is transient and there is a repair process that restores the faulty edge. Thus a min-cost arborescence \mathcal{T}_{f} in G-f is an interim min-cost arborescence—once the edge f is repaired, the original min-cost arborescence \mathcal{T} is restored. However another edge f^{\prime} might then fail. This sequence of edge failure, interim min-cost arborescence, and edge restoration is a recurring step. Our goal is to find each of the interim min-cost arborescences efficiently. Whenever an edge fault f happens, instead of computing a min-cost arborescence \mathcal{T}_{f} in G-f , can we find it more efficiently in real-time if there is a preprocessing step to do some preliminary work? Suppose the preprocessing step computes for each f\in\mathcal{T} , the min-cost arborescence \mathcal{T}_{f} in G-f and stores these n-1 arborescences as n-1 rows in a table. Then, whenever there is an edge fault f\in\mathcal{T} , we can fetch the appropriate arborescence \mathcal{T}_{f} from this table. But such a table would take \Theta(n^{2}) space. We seek a more space-efficient solution. This motivates the following problem. • Preprocess G=(V,E) and compute a sparse subgraph H=(V,E^{\prime}) such that it suffices to find a min-cost arborescence in H-f whenever an edge f fails. Such a subgraph H is a 1-edge fault tolerant (1-EFT) subgraph for min-cost arborescence in G . So what we store after the preprocessing step will be the edge set of H . Our objective is to find a sparse 1-EFT subgraph H so as to efficiently process each edge fault f by finding a min-cost arborescence in H-f (rather than in G-f ). For any directed graph G with edge costs, does there always exist such a sparse 1-EFT subgraph H ? Unfortunately, we do not know the answer to this question. We show the following result that if we are ready to pay the price of a small approximation factor, then there is indeed such a sparse subgraph. Theorem 1.1 . Let G=(V,E) be any directed graph with \mathsf{cost}:E\rightarrow\mathbb{R}_{\geq 0} . There is a subgraph H with O(n^{3/2}) edges (where |V|=n ) such that for any f\in E , the cost of a min-cost arborescence in H-f is at most twice the cost of a min-cost arborescence in G-f . We show a simple algorithm that takes O(mn+n^{2}\log n) time to construct the subgraph H in a preprocessing step. Thus, whenever an edge f fails, we run the algorithm of Gabow et al. [ 15 ] in H-f and find an arborescence of cost at most 2\mathsf{opt} in O(n^{3/2}) time, where \mathsf{opt} is the cost of a min-cost arborescence in G-f . So after each edge fault, our subgraph H provides a 2-approximate solution in O(n^{3/2}) time to our min-cost arborescence problem. Hence for a dense graph G , whenever an edge fault happens, we achieve significant time-saving at the cost of a 2-approximation. Furthermore, storing H takes only O(n^{3/2}) space. The unweighted setting. The above problem has been well-studied in the unweighted setting, i.e., when \mathsf{cost}(e)=1 for all e\in E . This is the k -fault tolerant single-source reachability subgraph ( k -FTRS) problem, where k is the number of edge/vertex faults. For any directed graph G on n vertices with a designated source, Baswana, Choudhary, and Roditty [ 2 ] showed there is a k -fault tolerant reachability subgraph of size O(2^{k}n) , where k is the number of edge faults. They also showed a matching lower bound of \Omega(2^{k}n) edges for

Read the complete text