WorksComputer Science
Exact minimum-cost arborescences under a single arc failure
Abstract
Every rooted weighted digraph on n vertices has a subgraph with arcs that contains a minimum-cost spanning arborescence after any feasible single arc deletion, answering a question of Dey and Kavitha. An oracle of the same size reports an optimal arborescence or a shortest list of arc replacements in time linear in the output. The construction uses shortest cycles in a weighted matroid exchange graph and admits deterministic subcubic preprocessing on simple digraphs. A reduction from directed distance preservation gives an -bit lower bound for reporting on simple digraphs with input arc identifiers, even with constant per-query error.
Introduction
Let be a directed multigraph with root , vertices, arcs, and a distinct identifier for each arc. A spanning arborescence is a directed spanning tree reaching every vertex from . For fixed arc costs, an exact preserver is a subgraph such that contains a minimum-cost arborescence of whenever one exists, for every allowed failure set , including the empty set. Queries are independent.
Dey and Kavitha [7 Theorem 1.1 and Section 5] give -arc preservers for factor-two approximation and ask for sparse exact preservers. We obtain exact preservation at the same size and preprocessing bounds and report optimal arborescences in linear time.
Theorem 1.1 (Arborescence preservation). For real costs, one can deterministically construct an exact single-arc-failure preserver of arcs and an oracle of records. The oracle reports an optimum arborescence or infeasibility in time. For a feasible query, it can report the additions and deletions relative to a fixed initial optimum in time, where is the fewest replacements among minimum-cost answers. Preprocessing takes
operations, where is the inverse Ackermann function and is the iterated logarithm. For polynomially bounded integer costs the first two terms in the minimum become and . The preserver itself can be constructed in time. We count exact cost operations and word-RAM operations with multiplication and division. Each identifier fits one word. For rational costs the bit complexity is polynomial. Root reachability detects initial infeasibility. At use the empty arborescence. Discard loops and arcs into .
The reduction applies to two matroids on a common ground set .
Theorem 1.2 (Weighted matroid intersection). Given a minimum-cost common independent set of cardinality , one can deterministically retain elements preserving the optimum at cardinality before and after every single-element deletion. An oracle of records reports an optimum or infeasibility in time. Preprocessing uses independence tests and further operations. At return the empty set.
Exact replacements from exchange cycles
Truncate the matroids to rank and fix a minimum-cost common basis . Write . The exchange graph has vertex set . For and , it contains an arc labeled by if is a basis of and is a basis of . The arc has length . Lengths are added coordinatewise and compared lexicographically. Loops are allowed.
Lemma 2.1 (Exchange cycles). Every directed cycle has positive length. For , a common basis avoiding exists exactly when a directed cycle through exists. A shortest such cycle has distinct labels and replacing its vertices in by its labels gives a minimum-cost common basis avoiding with the fewest outside elements. Conversely, the exchange bijections from any such basis produce a single shortest cycle through .
Proof. For a simple cycle of arcs and , form
where labels the corresponding arc. Replacing by leaves unchanged, since the heads and tails form the same multiset. Thus lies in both base polytopes and is a convex combination of common-basis indicators by matroid intersection [8].
Set
On every common basis this objective is lexicographically nonnegative. Since , the cost coordinate of is nonnegative. Its second coordinate is .
If , then , so the bases avoiding in the combination have total coefficient . At least one has objective at most , because the remaining bases have nonnegative objective. Every basis in the combination retains and draws its outside elements from the labels of , by the coordinates of equal to one and zero.
Conversely, let be a common basis avoiding . For each matroid there is a bijection from to with a basis. Indeed, after contracting , the exchange neighbors of any subset of the remaining elements of span that subset by fundamental circuits. The rank inequality gives Hall’s condition. The arcs labeled by form vertex-disjoint cycles of total length . Positivity makes the cycle through no longer than this total, with strict inequality if another cycle occurs.
Hence the shortest cycle length equals the minimum replacement objective. On a shortest -arc cycle the supported optimum must use outside elements, forcing all labels to be distinct and used. For a minimizing , the strict inequality above is impossible, so its bijections produce a single shortest cycle.
Keeping one cheapest arc per ordered pair leaves shortest cycle lengths unchanged. We use this compression when building the exchange graph explicitly.
Sparsifying the replacement paths
Split each exchange vertex into and , joined by a zero-length arc . Replace by , keeping its length and label. A simple path from to represents a cycle through . Every nonempty cycle in the split graph has positive length.
Lemma 3.1 (Path storage). Suppose every directed cycle in an -vertex digraph has positive length. Given one shortest path for each of finite demands, one can select at most vertices and designate some paths for explicit storage in time when . The explicit paths and the shortest-path trees to and from these vertices use arcs and records. They report a shortest demand path in time linear in its length plus one. For no records are needed.
Proof. Use the short-path and hub construction [5, 3]. A phase with remaining demands stores their paths of at most arcs. Greedily select vertices, or stop when all longer paths are hit. Each choice hits at least an fraction of the unhit longer paths, so at most demands remain. The phase stores arcs and records and selects vertices. Sum over the phases.
Each hit demand points to a selected vertex on its path. Concatenating a shortest path into that vertex and one out of it preserves the distance. A repeated vertex would yield a strictly positive cycle, so the concatenation is simple. Follow the two trees and reverse only the portion read backwards.
Maintain an incidence list for each vertex and place vertices in buckets indexed by their counts of unhit paths. Counts only decrease. A path’s first hit decrements its incidences in constant time each, and a maximum-count pointer scans at most buckets in a phase. The total incidence and initialization costs are .
Apply Lemma 3.1 to the finite demands . The preserver contains and the original labels of the stored arcs. Store the identifiers of in a deterministic static dictionary with constant lookup time, built in time and linear space [15]. Return or the empty change list for no failure or an absent identifier. For , an infinite distance signals infeasibility. A path with labeled arcs has arcs. The labels give the additions and their tails give the deletions. Lemma 2.1 gives the minimum change count. To report the full basis, scan with the deletions marked and append the additions.
For Theorem 1.2, enumerate both exchange lists of each outside element in independence tests. Updating the cheapest arc for each eligible pair costs operations. Dense all-pairs shortest paths and their trees take time, absorbed since . Choosing a tight predecessor or successor at each reachable vertex gives a tree, since cycles have positive length.
Preprocessing for arborescences
Use the graphic matroid on the underlying undirected multigraph and the partition matroid with capacity one per nonroot head. A common independent set of size is a spanning tree with one incoming arc per nonroot vertex, hence a rooted arborescence. Fix an optimum with arc entering . Each non-tree arc gives a transition for each edge of the undirected tree path .
Compute by Gabow, Galil, Spencer, and Tarjan’s implementation of Edmonds’ algorithm [11 Section 3]. It takes time using comparisons and additive cost updates. A tail-indexed array retains the cheapest arc per ordered pair in a sweep by head. Cost-zero dummy arcs into give strongly connected input to the algorithm.
Exchange graph representation
Path blocks. Subdivide , placing an edge atom at each midpoint and the empty set at each original vertex. Apply Alon and Schieber’s tree path algorithm [1 Section 3] with set union. Represent each nonempty preprocessing product by a block with zero-length arcs from its nonempty operands. Traversing the temporary gates of a query gives stored blocks whose union is the queried path. Connect each exchange copy to its singleton block with length . For each non-tree arc , connect the blocks for to with length and label . Keep the zero-length arcs .
The linear-space scheme with query time gives vertices and arcs. With , the constant-query scheme gives and . Either graph takes time to build. The tree edges that reach a block are exactly its atoms. Thus walks between exchange copies project to walks of equal length in the split exchange graph, and split-graph walks lift to the block graph.
Potentials. Record the minimum entering cost subtracted from each component when it is merged into a contracted cycle. The algorithm ends with one component, and the sets are laminar. Subtractions are nonnegative for nonsingletons, whose entering arcs have nonnegative residual costs at formation. An arc’s residual cost freezes at the first contraction containing both endpoints. During contraction, parallel arcs discarded earlier have residual cost at least that of their retained representative. Thus for every ,
The arcs retained in freeze at zero, so they attain equality. Expansion keeps connected by dropping one arc of each contracted cycle. If lies on , every component containing contains both endpoints of . Therefore . Use potential on both copies of and on block . All reduced lengths are lexicographically nonnegative. One traversal of the contraction hierarchy and a sweep of the block DAG compute these potentials in time.
Sparse preprocessing
Demand paths. Test reachability in for each . On feasible instances minimize to obtain in time, retaining the cheapest surviving arc per ordered pair under these costs.
The partition exchanges match arcs by head. For the graphic bijection, maintain a tree initially equal to , with fixed edges . Process edges in postorder of . The -component of is its descendant subtree in , since all missing edges below have been processed. Choose the first edge on the -to- path of . It crosses the cut of in , so is a tree. Match to , replace by in , and add to . Each remaining edge is a distinct member of . A link-cut tree [16] supports the search and swap in amortized time. Expose the path, descend using a subtree flag for nonfixed edges, and splay the edge found.
Lemma 2.1 turns the two bijections for into a shortest demand path. All demand paths take time, and Lemma 3.1 selects vertices. Run Dijkstra with Fibonacci heaps [10] in both directions from those vertices in the reweighted block graph with constant-time path queries. Contract each tree’s block portions to labeled transitions. A traversal tracks the nearest exchange copy and the intervening label, leaving records in time. All selected trees take time, within the same bound.
Distance computation. Compute the demand paths and selected trees from distances in a block graph. Append a hop coordinate of one to each reduced length and add a directed cycle of arcs with length , where is the largest reduced cost coordinate. Merge parallel arcs in time. Pettie’s comparison-addition algorithm [14] on the linear-size graph takes time. Coordinatewise additions and lexicographic comparisons implement the infinitesimal tie break. Below the added cost threshold, the first two coordinates give the reweighted distances. Tight-arc scans and contraction recover paths and trees within the same time.
For integer costs, pack a length as . This preserves the order of simple paths, whose lengths use at most arcs. If , singleton subtractions have magnitude at most and each nonsingleton subtraction is at most . Thus polynomial input costs give polynomial packed lengths. Orlin and Végh [13] spend time on preprocessing and per source. Run from the exchange copies in both directions. For either block graph this costs , giving the two integer bounds.
Dense preprocessing
For each head , root the undirected tree at . At , place the cheapest non-tree arc from to , if any. For an edge , the candidate tails for form the subtree cut off from by . A bottom-up pass finds the cheapest arc for each transition. Grouping by head gives the compressed graph in time. Dense all-pairs shortest paths with witnesses and Lemma 3.1 give time.
Subcubic multiplication. The min-plus algorithm of Essayag and Zabokritskiy [9 Theorem 1.1] extends to lexicographic lengths and returns minimizing indices. For input pairs , compare candidates via
This orders the sums lexicographically by cost, count and index. The sorted keys supply the rank and counting interfaces of their Sections 2 and 5 with -bit integer coordinates. Their final minimization identifies the winning index and length pair.
Min-plus squaring gives the lexicographic distance matrix , using zero diagonal entries to allow shorter walks. For the arc matrix of the -vertex split exchange graph, and give first and last hops for finite distances between distinct vertices. Encode absent entries of and infinite distances in by , where bounds the absolute cost coordinates in . A walk with such an entry and at most steps costs more than , which bounds all finite shortest simple path costs. The same threshold separates the outputs of the witness products. Cycle positivity makes the selected hops form shortest-path trees. The squarings and witness products retain the cited time exponent, giving preprocessing for real costs.
To construct the preserver alone, return when . For larger , the first sparse bound is .
Size equivalence and lower bounds
Let be the worst-case minimum size of a subgraph preserving exact distances for at most designated ordered pairs in an -vertex digraph with nonnegative real weights. Let be the worst-case minimum size of a single-failure arborescence preserver with real costs.
Theorem 5.1 (Equivalence of preserver sizes). For and ,
Proof. For the first inequality, use the compressed split exchange graph. The simple paths form a finite set, so preserves their order for sufficiently small . Cycles stay positive, and a shortest-path potential makes the scalar weights nonnegative. Retain the labels in a distance preserver for the demand pairs, together with . The empty subgraph suffices when the initial instance is infeasible.
For the reverse inequality, adapt the backbone construction of [4]. For the finite demands , add a disjoint zero-cost path . Choose larger than the cost of any simple path in the original graph. Add of cost and of cost .
When fails, an -to- path must make an excursion from to through the original graph, with . Its connectors cost . Each further excursion costs at least . Thus any path of cost below uses just the -th pair of connectors. The minimum is .
Root at and add zero-cost arcs from to all other vertices except the root. They complete any simple -to- path to an arborescence at the same cost. Conversely, nonnegative costs bound the tree cost below by its path cost. Restricting an arborescence preserver to the original arcs therefore preserves the demand distances. The case is trivial, and zero-cost leaves at pad the instance to vertices.
Theorem 5.2 (Space lower bounds). On simple digraphs with polynomially bounded nonnegative integer costs, single-failure preservers can require arcs. An oracle reporting from its stored state and the failed identifier can require bits on simple digraphs with fixed topology and costs and varying arc identifiers. With fixed identifiers and varying costs, the reporting bounds are bits for simple digraphs and bits for multigraphs. These bounds apply to full and replacement-list reporting with per-query error at most . For two arc failures, exact preservers have worst-case size . With arbitrary nonnegative integer costs, the same size is necessary for every fixed multiplicative approximation factor.
Proof. Use the layered distance-preserver construction [5, 4]. For take vertices with and . Put an arc of cost from to whenever both endpoints exist and . The demand from to has a unique shortest path with all increments , by strict convexity of the square. The demands indexed by and have arc-disjoint paths, since each of their arcs determines . Their arcs are forced in the backbone reduction, which has vertices.
For each forced arc, reserve a private pool of identifiers. Choose its identifier independently from that pool. The universe of identifiers has polynomial size, with all other identifiers fixed. The optimum before failure is the common zero-cost tree of the backbone and its terminal completion. After a backbone failure, the root-to-terminal path of any optimum reveals the identifiers on its demand path. Applying a replacement list to the common optimum recovers the same tree.
Let be the vector of independent uniform choices revealed by demand , with options per arc, and let and denote the oracle state and input-independent random coins. The success guarantee and Fano’s inequality give . By independence and subadditivity, . Taking gives the identifier bound.
For fixed identifiers in a simple digraph, give each vertex two clones with unit-cost arcs to it. Replace a transition to that vertex by two arcs to its clones. Choose one of cost and give the other cost . This adds a common unit cost per transition and encodes one bit in the leading arc of each forced transition. In a multigraph use parallel arcs with one of cost and all others of cost . Both constructions keep the common zero optimum and use a fixed exceeding all simple path costs. Their demand paths recover the choices with and .
For two failures, take zero-cost backbones and . Add of cost for . After deleting and , a surviving -to- path can use only and . Its unique cheapest crossing is . Complete paths to arborescences by zero-cost arcs out of as in Theorem 5.1. All crossing arcs are forced by varying the two failures. This is the weighted replacement-path construction of [4] with the terminal completion. For a fixed approximation factor , use crossing costs for an integer . Every other crossing available to a root-to-terminal path costs at least times the optimum, so the same arcs are forced by an -approximate preserver. These costs use bits per arc. For the matching upper bound, retain the three cheapest arcs of each ordered pair. After at most two failures, every discarded arc in a surviving optimum can be replaced by a surviving retained arc of no greater cost with the same endpoints.
Theorem 5.3 (Preprocessing lower bound). Under the directed -Cycle Hypothesis [6 Section 5], the worst-case deterministic preprocessing exponent of an exact oracle with replacement reporting is at least two, even on simple digraphs with arcs and polynomially bounded nonnegative integer costs.
Proof. Use deterministic color-coding [2] for each fixed . For a coloring with colors, keep arcs advancing to the next color in cyclic order. Split each vertex of color 1 into a source and a terminal . In this layered graph a path from to has exactly unit-cost arcs and certifies a directed -cycle. Use a family of polylogarithmic size that colors every -set injectively and try all color orders.
Apply the backbone construction to all pairs , with . At each backbone arc add a two-arc backup through a fresh vertex, with costs and zero, and include the fresh vertices in the terminal completion. The unique zero-cost optimum uses the backbone. After its -th arc fails, a path of cost below must use the -th connector pair, so its optimum cost is if the demand is reachable. Otherwise the backup gives cost $(q+2)M. In either case the path contains all other backbone arcs and completes to a tree with at most replacements. Thus the sum of the added costs in each replacement report tests reachability in time.
For an input with arcs, discard isolated vertices and pad each constructed graph with zero-cost terminal leaves to vertices. It is simple with arcs. Preprocessing in for a fixed would decide directed -Cycle for every fixed in time, contradicting the hypothesis.
Acknowledgment
Acknowledgment. The author used OpenAI models to formulate results, develop and review proofs, draft the manuscript, and implement finite checks. The source manuscripts [12] were prepared with GPT-6 Astra Pro.
References
- [1]N. Alon and B. Schieber. Optimal preprocessing for answering on-line product queries. Technical Report 71/87, Tel Aviv University (1987).
- [2]N. Alon, R. Yuster and U. Zwick. Color-coding. Journal of the ACM 42(4) (1995), 844–856.
- [3]G. Bodwin. A note on distance-preserving graph sparsification. Information Processing Letters 174 (2022), article 106205.arxiv.org/abs/2001.07741
- [4]G. Bodwin, F. Grandoni, M. Parter and V. Vassilevska Williams. Preserving distances in very faulty graphs. ICALP, LIPIcs 80 (2017), 73:1–73:14.arxiv.org/abs/1703.10293
- [5]D. Coppersmith and M. Elkin. Sparse sourcewise and pairwise distance preservers. SIAM Journal on Discrete Mathematics 20(2) (2006), 463–501.DOI
- [6]M. Dalirrooyfard and V. Vassilevska Williams. Conditionally optimal approximation algorithms for the girth of a directed graph. ICALP, LIPIcs 168 (2020), 35:1–35:20.
- [7]D. Dey and T. Kavitha. Low-cost arborescence under edge faults. arXiv:2605.13800v1 (2026).arxiv.org/abs/2605.13800
- [8]J. Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial Structures and Their Applications (1970), 69–87.
- [9]I. B. Essayag and A. L. Zabokritsky. Faster deterministic all-pairs shortest paths with real edge weights. arXiv:2611.17215 (2026).arxiv.org/abs/2611.17215
- [10]M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 34(3) (1987), 596–615.
- [11]H. N. Gabow, Z. Galil, T. Spencer and R. E. Tarjan. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6(2) (1986), 109–122.DOI
- [12]Yilin Liu and GPT-6 Astra Pro. Exact single-failure preservers. Algorithm Frontier, source snapshot 77140c2 (2026).
- [13]J. B. Orlin and L. A. Végh. Directed shortest paths via approximate cost balancing. Journal of the ACM 70(1) (2022), article 3.arxiv.org/abs/2007.07975
- [14]S. Pettie. A new approach to all-pairs shortest paths on real-weighted graphs. Theoretical Computer Science 312(1) (2004), 47–74.DOI
- [15]M. Ružić. Uniform deterministic dictionaries. ACM Transactions on Algorithms 4(1) (2008), article 1.DOI
- [16]D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences 26(3) (1983), 362–391.