WorksComputer Science
Online Survivable Network Design with Arbitrarily Small Connectivity Loss
Abstract
In the online survivable network design problem, a graph with edge costs is known in advance, and requests arrive one at a time. Each request is a pair of vertices with a connectivity requirement , and the algorithm must irrevocably buy edges so that and are joined by edge-disjoint paths. The goal is to keep the total cost close to that of an optimal offline solution. Gupta, Krishnaswamy, and Ravi~\cite{GKR12} obtain an -competitive algorithm, where is the maximum requirement, without relaxing the connectivity requirement. Dehghani, Ehsani, Hajiaghayi, Liaghat, and Seddighin~\cite{DEHLS18} obtain a polylogarithmic competitive ratio when the connectivity requirement is allowed to be relaxed by a factor of . We show that relaxing the connectivity requirement by a factor of only suffices to obtain a polylogarithmic competitive ratio.
Introduction
In online survivable network design, the network is known in advance but the pairs that need protection against edge failures arrive over time. On the arrival of a request, consisting of a pair and a requirement , an algorithm must buy enough edges to provide edge-disjoint – paths. Bought edges remain available, and their cost is paid only once. The objective is to compete with the least expensive network that serves all requests seen so far. Unlike ordinary online connectivity, this problem must preserve several independent routes while making irrevocable decisions about which routes to share. When requirements differ between requests, denotes the largest one.
Gupta, Krishnaswamy, and Ravi [1] gave a randomized -competitive algorithm that provides the full requirement . Their method uses spanning trees and an online covering problem whose explicit representation has size . A different direction is to relax the amount of connectivity. Dehghani, Ehsani, Hajiaghayi, Liaghat, and Seddighin [2] obtained polylogarithmic bicriteria guarantees by providing only edge-disjoint paths when all requirements equal . In the rooted case, their competitive ratio is ; for arbitrary pairs it is .
These results leave a natural question: is a loss of half the connectivity necessary to obtain a competitive ratio independent of ? We show that it is not: every prescribed relative slack is sufficient. Fix any . For a request with requirement , our algorithm always provides edge-disjoint paths. Its expected cost is compared with the cheapest network that provides all paths, and its competitive ratio is polylogarithmic times . When all requirements equal , the competitive ratio is , and if moreover is at least a constant fraction of , the competitive ratio drops to . When requirements differ, every request still receives a fraction of its own requirement, rounded up, and the competitive ratio is .
This competitive ratio does not grow with the largest requirement, and the algorithm does not need to know that requirement in advance. The algorithm runs in polynomial time in terms of the input size, regardless of the value of . It is randomized, never fails to provide the promised connectivity, and its cost guarantee holds in expectation at every point of a request sequence that is fixed in advance. More generally, when all requirements equal , we show how the cost changes when the algorithm provides any number of paths: what matters is the slack . Whether exact connectivity admits a competitive ratio polylogarithmic in remains open.
Preliminaries
The input is a known loopless undirected multigraph with vertices and edges. Parallel edges are allowed. Each edge has a nonnegative rational cost , and for a set of edges we write . Each edge has unit capacity and can be bought at most once. Edges with the same two endpoints form a parallel bundle. We identify a set of edges with the spanning subgraph of that it forms; in particular, connectivity in a set of bought edges refers to the graph . For a vector and we write and . Throughout, is to an arbitrary fixed base, is the natural logarithm, , and is the indicator of an event. The notation means , and hides a factor depending only on the parameter .
A shore is a set of vertices . For a subgraph of , the set consists of the edges of with exactly one endpoint in . A shore separates two vertices if it contains exactly one of them. A – separator in is a set of edges of whose removal leaves no – path. A separator is identified by its edge set and a shore by its vertex set; in our parity construction these need not carry the same information. The connectivity is the minimum size of a – separator in ; a separator of this size is a minimum separator. By the edge version of Menger’s theorem, this equals the maximum number of edge-disjoint – paths in . A minimum-cut shore for in is a shore separating with . All connectivity computations use unit capacities on edges; costs are never used as capacities.
Requests arrive one at a time, for . Each request has distinct endpoints and a positive integer requirement . We assume the requests are feasible in , that is, ; thus every requirement is at most . Disconnected inputs are treated component-wise; we describe one connected component. The requests are rooted if all of them share a common endpoint. The first requests form the prefix . When describing an algorithm, we write for the pair of the request being processed. Requirements are uniform if all of them equal a common value , known in advance; in that case we write instead of . In general, refers to the largest requirement, which our nonuniform algorithm does not need to know. An online algorithm maintains a set of bought edges, which only grows. After request is processed we denote it by , and the algorithm pays in total.
For a parameter , a positive rational when supplied as input, the algorithm must ensure for every . We say that it violates the connectivity requirement by a factor of , and call its connectivity loss. Providing only half of each requirement corresponds to loss 2. For uniform requirements we also study an arbitrary integer target , so that every requested pair must have connectivity at least in , and we call
the slack. The headline case is .
A request sequence is oblivious if it is fixed independently of all algorithmic randomness; expectations and probabilities are over the algorithm’s random choices. The cuts computed internally by the algorithm may depend on its complete purchase history.
For a prefix , let be the set of shores separating at least one requested pair with . With common full requirement , define
Its integral counterpart, with , is : the cost of the cheapest set of edges that gives every requested pair connectivity . The bounds reflect the unit capacities and are essential to our analysis. For nonuniform requests, and are defined in the same way, except that a shore separating must be crossed by mass at least . In every case . An algorithm is -competitive if for every prefix of every oblivious sequence. All our bounds are stated against , which is stronger.
Let be a spanning tree. For vertices , let be the unique – path in , and let be its cost; tree edges keep their original costs. For an edge with endpoints and we write and . An edge is a chord, and its fundamental cycle is . A polynomial-time spanning-tree sampler has stretch if it outputs a random spanning tree satisfying
We take . A spanning tree is sampled when it is drawn from such a sampler; all later random choices are independent of it. In the headline bounds we use from [3]; the full tradeoff below keeps explicit. Our direct-cut algorithm does not use the sampler.
Our results
Theorem 1.1 (Uniform requirements). For every and known common requirement , there is a randomized polynomial-time online algorithm that always provides edge connectivity for all arrived pairs. For every fixed prefix of an oblivious request sequence,
This holds for arbitrary multigraphs. In particular, if for a fixed , the competitive ratio is and is independent of the spanning-tree sampler.
The graph, , and determine which of our two algorithms is used; the choice is made before the requests arrive. One factor in (3) comes from discarding all but the cheapest edges in each parallel bundle, a reduction that preserves both benchmarks. Before this reduction we prove the following more precise tradeoff.
Theorem 1.2 (The full connectivity–cost tradeoff). Fix integers . For a common full requirement , the parity-cover algorithm supplies connectivity at expected cost at most
For , its bound is exactly . The direct-cut algorithm supplies the same target at expected cost at most
Both algorithms are polynomial time, are feasible on every execution, and satisfy the displayed bound at every fixed oblivious prefix.
The denominator in both bounds is the slack . At , the parity bound still has a factor . Thus the endpoint of the theorem is a polynomial implementation of an exact-connectivity guarantee with this dependence; it does not give an exact polylog result in general.
Theorem 1.3 (Nonuniform requirements). For arbitrary online requests and fixed , there is a randomized polynomial-time algorithm that always provides edge connectivity for each request and satisfies
at every fixed prefix of an oblivious sequence. No upper bound on future requirements is needed. In particular, the competitive ratio has no additional factor depending on the maximum requirement.
For the original vertex-arrival formulation, take the first terminal as a root and request a pair between that root and every later terminal. Providing connectivity from every terminal to the root provides connectivity between every two terminals: a cut separating two terminals separates at least one of them from the root. Thus our arbitrary-pair theorems include that formulation.
The logarithmic spanning-tree theorem of Hajiaghayi [3] provides a polynomial-time construction with . This is the tree input used in Theorems 1.1 and 1.3. Consequently, uniform requests on arbitrary multigraphs, and nonuniform requests on simple graphs, both admit a competitive ratio of . The stronger connectivity-dependent bound in (3) applies to the uniform case.
This stretch matches the lower bound of Alon, Karp, Peleg, and West [4], which already holds for the average stretch of a single spanning tree. The result of [3] is an external input to this paper. The proof of Theorem 1.2 works with any sampler satisfying (2). For completeness, Appendix A also records how the published average-stretch bound of Abraham and Neiman [5] yields such a sampler. The main approximation bounds use the logarithmic theorem of [3]; with the Abraham–Neiman bound instead, every use of costs an additional factor .
Comparison and related work
Table 1 records the main comparison. Our improvement is in the permitted connectivity loss, in the treatment of arbitrary requirements, and in the dependence on connectivity within the new tradeoff. For example, the deterministic competitive ratio of [2] for rooted uniform requests remains better at loss two in some parameter ranges. We do not improve every earlier special case.
Online Steiner tree and forest are the requirement-one cases, studied by Imase and Waxman [6] and Berman and Coulston [7], among others. Offline survivable network design admits Jain’s factor-two approximation [8]. In the online setting, a logarithmic lower bound is already known for rooted requirement two [1 Appendix A]. Naor, Umboh, and Williamson [9] improved the special case of maximum requirement two through online weighted tree augmentation.
Table 1. All cost bounds use the optimum for the full requirements. The guarantees of this paper hold against the capacitated cut LP. Our algorithms are randomized against oblivious arrivals; the cited loss-two algorithms are deterministic.
For nonuniform requirements, the bicriteria framework of [2] incurs a factor in the maximum requirement and loss for a constant . Our nonuniform algorithm handles all requirements in one covering process. Its proof uses residual multiplicities instead of partitioning requests into requirement classes.
Online covering and primal–dual growth are standard tools [10, 11]. Borst, Eliáš, and Venzin [12] use a model of semi-adaptive adversaries as a key ingredient for online node-weighted Steiner forest. Our analysis faces a related issue: a minimum cut depends on previous random purchases, so we prove one exponential-moment inequality for each member of a fixed shore family. The new quantitative ingredients are the multiplicity discount, the coordinate cap, and the connectivity-rank bound on the number of repairs.
Fixed-base connectivity augmentation has also seen recent progress. Garg and Subramanian [13] study online augmentation of a given -edge-connected graph, where each arriving pair must become -edge-connected; they obtain deterministic and, for weighted links, competitive ratios. Garg, Hommelsheim, and Lindermayr [14] obtain a deterministic weighted bound for pair arrivals. Hathcock, Subramanian, Umboh, and Zlatin [15] obtain nearly logarithmic weighted bounds in the cut-arrival model. These results start from a fixed globally -edge-connected graph. Our bought graph grows with the requests, and unrequested Steiner vertices need not have high connectivity.
Finally, (2) requires spanning trees made of input edges. A distribution over arbitrary tree metrics, such as the Fakcharoenphol–Rao–Talwar embedding [16], does not by itself provide the physical cycles used in our algorithm.
Our Approach and Techniques
From deficient cuts to many interchangeable witnesses
Fix a common full requirement , and suppose we only need to provide connectivity. Write
The central observation is that a cut of the bought graph with edges leaves at least choices in any full- solution. To exploit those choices, however, we need a covering constraint that does not depend on unbought parts of the network in an uncontrolled way. The parity construction supplies such a constraint while retaining all witnesses.

Figure 1. A chord joining opposite parity classes has a fundamental cycle with odd intersection with . The path shown has three edges of ; only their parity matters. The shore need not be a minimum-cut shore of the bought graph.
Sample one spanning tree at the beginning. On a request , buy the tree path . The remaining decisions are purchases of fundamental cycles
at prices . These prices may overcount previously bought edges, which is harmless. They also give a fixed price to each of at most choices. Expected tree stretch will later compare their prices with the original cost of one fixed offline solution.
Suppose the bought graph still has an – minimum separator of size . Root at a reference vertex. Give each vertex the parity of the number of edges of on its path from the reference vertex, and let be the vertices with odd parity. The already bought – tree path meets oddly, so separates the requested pair. A chord in
has a fundamental cycle that meets oddly. Purchasing that cycle destroys as a separator. The reason is elementary but useful: if remained a separator, its minimum cardinality would force it to be a cut of the enlarged graph, whereas every cycle crosses a cut an even number of times.
Every full- solution has at least edges across . Deleting excludes at most of them. Hence
Putting value on every comparator chord gives one fractional cover of every row the algorithm may expose. For a cut-LP solution , the same calculation is , so the comparison extends to . This is the source of the improvement as the target falls below . We use all available witnesses, even though the algorithm only has to buy one cycle to destroy the current separator.
Why capping helps both the algorithm and the bound
The rows are not listed in advance. The algorithm finds one deficient cut, forms its parity row by a tree traversal and an edge scan, and processes that row. A fractional variable records investment in cycle . On an unhit row , the update is a cost-scaled multiplicative increase with a small additive seed:
Each increase also offers a fresh chance to buy the cycle, with probability proportional to . Here is an amplification parameter determined by how many different shores may witness a repair. A coordinate is frozen after its cycle is bought.
The crucial additional rule is deterministic: buy a cycle as soon as reaches . Thus the fractional process never needs to invest substantially beyond the scale at which rounding should have selected the cycle. Allowing a constant overshoot gives . The usual multiplicative-growth calculation then bounds the total dual load on an edge by
instead of . Combining this with (7) gives fractional cost . Random purchases and threshold purchases multiply this bound by . The resulting expression is
It remains to justify a small enough amplification parameter despite the dependence of future cuts on past purchases.
Counting tree shores instead of failed edge sets
A direct union bound over all separators would count subsets of edges. The parity shore depends only on , so a much smaller description uses subsets of the tree edges. The nontrivial issue is that many different rows can have the same parity shore: they can exclude different bought chords. We therefore track two quantities for each fixed shore :
where is the set of selected chords. Fractional investment increases , while actual purchases increase . With , the process
is a nonnegative supermartingale. Fresh independent coins make the expected decrease caused by purchases cancel the increase caused by fractional growth. Deterministic purchases can only decrease it. This calculation is conditional on the entire history, and therefore allows the next row to be chosen adaptively.
If a row reaches mass one without selecting a cycle, we force a cheapest purchase. At that moment . Moreover, every already selected chord crossing belongs to : otherwise its cycle would already have destroyed the separator. Thus . A forced repair requires the fixed-shore process (8) to reach at least .
There are only
possible nontrivial parity shores. A maximal inequality and a union bound over these fixed shores control all adaptive repairs at once. We never enumerate the shores. Their number determines , and only its logarithm appears in the cost.
One more observation is needed on multigraphs. Bounding the number of repairs merely by would introduce an unnecessary term into the probability budget. In the virtual graph , consider, for every level , the partition into -edge-connectivity classes. The first new chord selected while processing a row joins vertices with connectivity below . Adding that chord merges two classes at some level. The sum of the numbers of such mergers is at most . This gives a deterministic bound on all row procedures, including forced repairs, that depends on vertices and connectivity rather than on parallel multiplicity.
Consequently we can take . Together with , the cap gives the product
in (4). Finally, requested tree paths cost at most times the comparator’s total tree distance: each used tree edge defines a cut crossed by at least comparator edges. Averaging the cycle and path charges over contributes .
The second algorithm: pay for all shores and avoid the tree
The parity construction reduces the number of shores, but it pays for fundamental cycles. When is large, we can afford a larger shore family and save that tree cost entirely.
For this algorithm, take an actual deficient minimum-cut shore of the bought graph and expose
The objects are now individual edges, at their original prices. Every full- comparator again contributes at least available edges. Run exactly the same capped growth and purchase procedure on . An edge in increases the size of this particular cut; the algorithm then recomputes a minimum cut until the request is served.
There are fewer than canonical vertex shores. At a forced repair, at most bought edges cross its shore, so the same potential (8) applies. The connectivity partition potential now includes level one, allowing the bought graph to begin disconnected. It bounds the number of procedures by . An amplification of therefore suffices. The capped-growth bound becomes
The factor comes from the logarithm of the number of shores, and the denominator comes from the number of comparator witnesses. For and , those factors cancel up to . This explains the logarithmic cost bound without a tree-embedding factor.
Nonuniform requirements in one covering process
For a request of requirement and a deficient cut of size , the parity row contains comparator mass at least . Rather than normalize every row by a common slack, we grow its fractional mass toward , using an additive seed . The dual objective charges that update in proportion to . At the relaxed target,

Figure 2. The two algorithms make complementary choices. The first compresses the shore family using a tree; the second avoids the cost of tree paths. Their quantitative bounds can be compared before the arrival sequence begins.
Thus a repair at a separator of size requires investment exceeding . The probability of such an event decreases exponentially in , while the number of formal separators of size is at most . Choosing amplification makes the sum over all separator sizes converge. This is why no requirement classes, advance maximum, or extra logarithm in the maximum requirement are needed.
Preliminaries and purchase accounting
For a graph , let be its edges with exactly one endpoint in , and let be the minimum size of an – edge cut. By the edge version of Menger’s theorem, this is also the maximum number of edge-disjoint paths. Costs are not capacities: all connectivity computations use unit capacities on bought edges. A separator is identified by its edge set; a shore is identified by a subset of vertices. These need not carry the same information in the parity construction.
The algorithm’s bought graph is always the union of its purchases. For the parity algorithm, selecting chord means buying every missing edge of . We charge the full price , even when part of that cycle is already present. Each selected chord is recorded once in . Requested tree paths are charged separately by the cost of their union. Thus these charges are an upper bound on the amount actually paid.
Zero costs. Buy all zero-cost edges initially. For the parity algorithm, choose a zero-cost spanning forest inside each zero-cost component, sample a tree after contracting those components for the purpose of tree selection only, and lift the sampled tree using that forest. Every zero-cost edge then has a zero-cost tree path. Include all zero-price chords in initially. A violated row never contains an object already selected, so all update denominators are positive. The original vertices and all unit-capacity edges are kept for connectivity computations. Contracting zero-cost components in those computations would be incorrect.
Fixed-prefix comparisons. Throughout a cost proof, fix a finite prefix of the external sequence and one feasible vector for its full-requirement cut LP. This vector is independent of the sampled tree and all purchase coins. It is used only in the analysis. The algorithm never needs the future prefix, an optimum, or the value of LP.
Algorithm 1: CoverRow($A$): shared capped purchase procedure
Input: A nonempty row $A \subseteq U \setminus I$; fixed prices $d_e > 0$.
1: while $A \cap I = \varnothing$ and $\sum_{e \in A} x_e < 1$ do
2: $\gamma \leftarrow (\eta/4)\min_{e \in A} d_e$.
3: Compute $\Delta_e \leftarrow (\gamma/d_e)(x_e + 1/m)$ for every $e \in A$.
4: $x_e \leftarrow x_e + \Delta_e$ for every $e \in A$, simultaneously.
5: Independently mark each $e \in A$ with probability $\operatorname{Dyad}(\min\{1,a\Delta_e\})$.
6: Select every marked object and insert it into $I$.
7: Select every remaining $e \in A$ with $x_e \ge 1/a$; insert it into $I$.
8: Finish this entire batch before inspecting another row.
9: if $A \cap I = \varnothing$ then
10: Select a minimum-price object of $A$ and insert it into $I$. \{forced repair\}
Capped covering with adaptively exposed rows
We prove the common rounding lemma once. Let be a fixed set of at most objects with positive prices . The algorithm maintains an initially empty selected set on its positive-cost objects and nonnegative variables , initially zero. A coordinate stops changing once its object is selected. A row is a nonempty set ; rows may depend on the entire preceding history.
Fix an integer amplification , and put
For , let be the smallest number of the form , , that is at least ; set . The selection rule is explicit and uses only fair random bits.
After conditioning on any preprocessing randomness, all prices, shore incidences, and parameters below are fixed. We assume that, in the prefix under analysis, one fixed nonnegative vector , independent of the subsequent purchase coins, satisfies for every row that can be exposed. Here , , and are positive integers. We also assume a deterministic upper bound on the number of row procedures. To bound repairs, associate each row with a member of a fixed family of size at most . Each member has a fixed incident object set . At every forced repair of row associated with , require
These hypotheses concern only the repair state. The family can be exponential and need not be generated.
Lemma 4.1 (Capped adaptive covering). Under the preceding assumptions, if
then Algorithm 1 has expected total selection price at most
Every call selects a new object, and each call performs updates for every .
Fractional growth and the cap
An active coordinate is below . Since and , a simultaneous update satisfies
Consequently at all times and . A coordinate that crosses its threshold is immediately selected and frozen. If is its fresh coin probability, then
Let . Assign a dual charge to each fractional update on row . For a fixed object , the update identity is
Because and on this interval,
Each update begins with , so
Using and summing gives the pathwise inequality
The rows need not all become fractionally covered. An early integral purchase may end a row procedure before its mass reaches one; the dual-load argument still applies.
Conditional on the history just before an update, its expected coin purchase price is at most , by (14). The total threshold price is at most on each execution, since every threshold purchase has and occurs only once. Thus these two types of purchases have expected price at most .
One exponential moment for each fixed shore
Fix and consider checkpoints after each complete update-and-purchase batch and immediately before each forced repair. Define
The increments are determined before the fresh coins. A coordinate is updated only when unselected. For each updated incident object, its independent coin gives a purchase indicator with probability . Therefore
The first inequality allows additional threshold purchases. This cancels the factor from the increase of . Forced purchases also only decrease . Hence is a nonnegative supermartingale with initial value at most one.
At a forced repair, the current row has mass at least one. By (10), its associated shore has and . Thus . The maximal inequality for a nonnegative supermartingale, followed by a union bound over the fixed shore family, yields
For a direct proof of the maximal inequality here, stop the process at the first threshold crossing or at the last checkpoint. Its expectation is at most one, so the crossing probability is at most the reciprocal of the threshold. The number of updates is bounded deterministically below, and no limiting stopping argument is needed.
Since , the cheapest object of any exposed row costs at most . At most repairs occur. Their total price is therefore at most on any execution and is zero unless the event in (17) occurs. Its expectation is at most . Together with (16), this proves the cost bound.
Termination of a row procedure
Within one row , fix a cheapest member . Until the procedure ends, every update multiplies by . Starting from zero, it reaches the threshold within
updates, unless another purchase or a forced repair ends the row earlier. If , then , so the bound is . If , put . The inequality shows that at most four updates suffice. This completes the proof of Lemma 4.1.
The parity-cover algorithm
Fix a sampled tree , rooted at a reference vertex . For any edge set , define
The identity
holds for every : the parity label flips across exactly those tree edges that belong to .
Lemma 5.1 (Parity and multiplicity). Suppose contains and every cycle for . Let be a minimum – separator of , of size . Then separates , all members of are chords, and . Adding for any destroys as a separator. Every feasible full- cut vector for this request satisfies
Proof. Let be the vertices reachable from in . Then ; minimum cardinality gives equality. The bought tree path from to crosses this cut oddly, so . By (20), a tree edge outside has equal labels at its endpoints. Thus contains only chords.
Algorithm 2: Uniform parity cover for a common full requirement and target
Sample satisfying (2); choose a reference root .
Buy zero-cost edges; put their zero-price chords into .
For every other chord , set and .
If , set and from Section 9.
for each arriving pair do
Buy every missing edge of .
while do
Compute a minimum – separator in .
Traverse to compute and in (19).
Form by scanning ; call .
A selected object buys the whole cycle .
For with endpoints , its fundamental cycle satisfies
Suppose still separated in , and let be the vertices reachable from in . Then
It follows that , contradicting the even intersection of a cycle and a cut. In particular, a cycle already contained in cannot have its chord in .
Finally, separates the request, so . Removing loses at most units because . This proves (21). □
The loop recomputes a minimum cut after each call. Repairing one separator need not increase the minimum-cut value immediately. For , only requested tree paths are purchased.
A bound on the number of row procedures
For an integer , the relation if or is an equivalence relation on the vertices of any undirected graph . For transitivity, every cut separating separates at least one of the pairs and . Let be the number of equivalence classes. Adding edges only merges classes.
Lemma 5.2 (Connectivity-rank bound). For , the total number of row procedures in Algorithm 2 is at most
Proof. Use the virtual graph and the integer potential
It is nondecreasing and at most . Immediately before the first new chord selected in a row for , with endpoints ,
Indeed, (20) accounts for all crossing tree edges, and Lemma 5.1 forces all previously selected crossing chords into . Thus . Adding the edge increases every – cut by one, so the new connectivity is exactly . The -connectivity classes containing and merge, and increases by at least one. Further purchases cannot decrease it. Each procedure also selects a distinct chord, proving both bounds in (23). □
The virtual tree is used only in this proof. Its edges are paid for when requested paths or selected cycles use them; no free physical capacity is assumed.
Applying capped covering
Fix a prefix, its cut-LP comparator , and . Put and
By Lemma 5.1, covers every row. A canonical parity shore is determined by a nonempty subset of at most tree edges, hence the shore family has size at most
Restrict the covering universe and to positive-price chords; free chords were selected initially and never occur in a row. Take to be the positive-price chords in . At a repair for , its row is contained in and all selected chords crossing lie in . More precisely,
because the requested tree path forces . The weaker bound suffices for Lemma 4.1. For an amplification satisfying (11) with and , the conditional expected cycle charge is at most
Let be the union of requested tree paths in the prefix, excluding extra tree edges bought only through cycles. For each tree edge , let be a component of . Double counting gives
since every separates a requested pair. Averaging over yields
Here was fixed independently of , so and are legitimate applications of (2). Choosing an optimum proves the exact parameter form of the parity bound. Its simplification is given in § 9. Feasibility follows because every deficient request supplies a nonempty row and each call buys a new chord; by Lemma 5.2, the process cannot continue indefinitely.
Algorithm 3: Uniform direct cuts
Buy all zero-cost edges; initialize and on positive-cost edges.
Set , , and .
for each arriving pair do
while do
Compute a minimum – cut shore in .
Set .
Call CoverRow; selecting buys that original edge.
The direct-cut algorithm
There is no spanning tree in the second algorithm. Its objects are the original positive-cost edges, at prices . All zero-cost edges are present initially. Whenever a request has connectivity , find an actual minimum-cut shore and expose
Run CoverRow on this row with amplification specified in Section 9. Selection buys the individual edge.
For any fixed full- cut vector ,
Thus covers every exposed row. To bound the number of procedures, use
For the first edge selected in a procedure, with endpoints , we have . Adding merges the -connectivity classes of and . Therefore each procedure increases by at least one. The number of procedures is at most
Represent every nontrivial shore by its side excluding one fixed reference vertex. There are fewer than such shores. For each shore, take restricted to positive-cost objects. At a forced repair, , and at most selected objects cross . The hypotheses of Lemma 4.1 apply. With amplification satisfying (11), they give
The choice will prove (5). This algorithm has no tree charge.
Removing excess parallel edges
Lemma 6.1 (Parallel-bundle reduction). For a known common requirement , retain the cheapest edges of each parallel bundle, or the entire bundle when it has fewer than edges. This preserves and for every request prefix. The retained graph has at most edges.
Algorithm 4: MultiCoverRow(A, b) for a nonuniform request
while and do
.
Compute for every .
Increase all simultaneously by .
Independently select each with probability .
Buy every selected cycle, insert its chord into , and finish the batch.
if then
Buy a cheapest cycle of and insert its chord into .
Proof. For any feasible full- vector , let be its total mass in one bundle. Replace this mass by , assigned to the retained edges in nondecreasing cost order, at most one unit per edge. This does not increase cost. A cut contains either an entire bundle or none of it. If all its crossing bundles had mass less than , its total mass is unchanged. If some crossing bundle had mass at least , that bundle alone retains units. Thus every required cut stays feasible after all replacements. Conversely, a solution on retained edges is a solution on the original graph. The same argument preserves integrality because integer bundle masses are assigned integrally. This proves both equalities of optimum values and the edge-count bound. □
The reduction uses the known common requirement. We do not apply it to the nonuniform algorithm, whose future maximum is unknown.
Arbitrary requirements without requirement classes
We now prove Theorem 1.3. Keep the parity construction and cycle prices, but replace the uniform normalized process by fractional multicover growth. Fix , and let be the amplification chosen in Section 9. Initialize for every chord, and initialize with all zero-price chords, whose cycles have been bought for free. As before, selected coordinates are frozen. On request , first buy its tree path and set .
If a minimum separator has size , form and set . The parity lemma, with in place of , gives
for every fixed full-requirement comparator . The middle inequality follows from .
After each call, recompute a minimum cut and continue until the current target is met. There is no deterministic cap in this version; the varying row threshold provides the needed growth bound. At most row procedures occur because each selects a new chord.
One comparator for all residual thresholds
Fix a prefix and its feasible cut vector . Let ; this is an analysis parameter, not an input to the algorithm. Put
An updated coordinate has pre-update value below ; since , it always remains at most . For ,
The same logarithmic calculation as in (16) gives
The increase in fractional cost at update is less than . Using , we obtain
The dyadic coin rule satisfies and , including when . Hence expected sampled price is at most .
A repair bound stratified by separator size
Fix a formal edge set of size , and its row , whether or not that row is ever exposed. The process
is a nonnegative supermartingale. If the row remains unhit, fresh coins give survival probability at most , canceling fractional growth; a purchase in the row makes the process zero forever.
A forced repair of this row occurs only after its mass reaches . Its probability is therefore at most , by the same maximal inequality used in § 4. There are at most formal edge sets of size . Choosing gives
This sum does not enumerate rows in the algorithm. It is a probability estimate over the fixed implicit family.
By (32), a cheapest row cycle costs at most . There are at most repairs, so their expected price is at most . Altogether the conditional expected cycle price is at most
Each tree edge in the union of requested paths defines a cut with comparator capacity at least one. Thus its union costs at most . Averaging over the tree gives
The parameter estimates in Section 9 finish the proof of Theorem 1.3.
Implementation and running time
Let be the number of requests processed. All algorithms use ordinary minimum-cut computations in the currently bought unit-capacity graph. Fix deterministic tie breaking for cuts and minimum-price objects; their particular choices do not affect the proof. Computing a parity row takes one traversal of and one scan of . An actual-cut row takes one edge scan. Cycle prices are computed once; the algorithms never change those prices to reflect earlier purchases.
Let be the running time of any polynomial-time minimum-cut routine for one pair. The uniform algorithms make such calls, where or . They perform fractional updates, each scanning at most objects. Expanding the paths of all selected cycles takes at most additional work by a direct implementation; requested tree paths take at most . These bounds give, after tree preprocessing where applicable,
arithmetic and graph operations. The direct-cut algorithm omits the path-expansion work. Sorting parallel bundles for Lemma 6.1 takes comparisons.
For a nonuniform row, a cheapest member satisfies
It reaches mass within updates unless a purchase ends the row earlier. Thus the nonuniform algorithm has the same bounds with . In particular, no loop has length proportional to or to an unknown maximum requirement.
The algorithms require no real-exponential sampling. A coin of probability is implemented by testing whether fair bits are all zero. The integer amplification parameters below are obtained by binomial recurrences, integer powers, and comparisons. All costs and updates are rational. Each update multiplies or adds rational quantities determined by input prices and the displayed parameters; over the polynomially many updates, their representations remain polynomial in the input length. Consequently the algorithms have polynomial running time with exact rational arithmetic and fair random bits, as well as the explicit operation bounds above.
Choosing the parameters
We now set all amplification constants and verify the inequalities used in the analysis. Natural logarithms are denoted by ; changing bases in asymptotic expressions affects only constants. The case is served by its only edge when requested, so assume .
Uniform parity cover
For , let be given by (22) and (24), and set
Since ,
This verifies (11). Also . For , the binomial estimate gives the needed entropy bound. For larger , use . Together these imply
Furthermore , and hence . Both terms are : the first is , and is increasing on . Consequently
The additive in (28) is absorbed by : here , and is bounded below by a positive constant. Using proves (4).
For the running-time condition, , , , and imply
Thus , as required for (19). The binomial sums have polynomial-size integer representations and are computed without enumerating their subsets.
Uniform direct cuts
For , set
Again , proving (12). The identity and the bound give
Substituting these estimates in (31) proves (5). This completes Theorem 1.2.
The near-exact target and the best of the two algorithms
Let . The ceiling is useful:
For every , also and . Therefore the parity guarantee is
and the direct guarantee is
For , the tree-path guarantee is already at least as strong as the asserted asymptotic parity bound.
Apply Lemma 6.1 before choosing an algorithm. Both logarithms involving in Equations (42) and (43) are then , because . The backbone term in (42) is absorbed. Choosing the algorithm with the smaller of these known upper bounds and substituting from [3] proves Theorem 1.1. More concretely, use a declared rational upper bound on the sampler’s stretch. For , replace in Equations (28) and (31) by the rational bound
and compare the two resulting coefficients, using in place of . These replacements change each bound by at most an absolute constant for the chosen parameters. Choose the smaller coefficient; for , use tree paths. The comparison uses integer arithmetic and no information about the arrival sequence.
For example, if for fixed , the competitive ratio of the parity-cover algorithm, apart from the factor , is at most . If , the competitive ratio of the direct-cut algorithm is . These parameter improvements do not reduce the worst-case logarithmic exponent uniformly over all .
Nonuniform requests
Take
Then , the condition used in (34), and . Feasibility gives , so . Substitution in (36), together with from [3], proves (6). The algorithm uses only and in this choice, not .
The remaining exact-connectivity question
The positive results above isolate the role of slack. A deficient separator of size has certified comparator witnesses. At exact connectivity, a final separator can have , so this guarantee supplies only one witness. Our proof then loses its discount while the family of possible separators can still be large. No general exact polylog bound follows from the analysis.
The logarithmic lower bound already known at small fixed connectivity [1] does not imply that polynomial dependence on is necessary. In particular, a construction with competitive ratio on vertices remains a logarithmic-size lower bound even after writing . We make no universal lower-bound claim polynomial in .
There is nevertheless a concrete obstruction to a natural completion argument. Appendix § 13 gives a simple graph with one request, , and equal fractional and integral augmentation optima. Independently rounding one optimum fractional solution needs amplification for constant success probability; smaller amplification can leave a constant fraction of the optimum to be paid in repairs. This rules out that particular independent-rounding estimate. A successful exact-completion algorithm could instead exploit correlations, adaptivity, or a different fractional representation.
AI Use Statement
This work resulted from extensive interaction between the authors and OpenAI Astra, with the authors providing suggestions and critically checking Astra’s responses through iterative exchanges. OpenAI Astra was also used in writing and revising the manuscript through detailed prompts from the authors, with Gemini Argon assisting in some parts. The authors directed the process and evaluated the proposed ideas and arguments. Lean files formalizing the main theorem are available on GitHub at https://github.com/hajiaghayi/Online-Survivable-Network.
Constructing a spanning-tree distribution from average stretch
This appendix records a polynomial-time route to the older published stretch bound. The headline results instead use the sharper logarithmic theorem of [3]. It also explains why an average-stretch statement suffices for the per-edge expectation in (2). The reduction uses the spanning-tree game of [4] and the average-stretch algorithm of [5].
First assume a simple graph with positive rational edge lengths. Write , and let be an integer upper bound for the average-stretch guarantee on graphs with vertices. For a rational distribution on the edges, replace edge by parallel copies of the same length. Their total number is at most , and . An average-stretch tree on this replicated graph therefore gives
To use an average-stretch algorithm stated for simple graphs, subdivide each copy into two half-length edges. There are vertices. In a spanning tree of the subdivision, each new vertex is either a leaf or has both incident edges present. The copies with both halves present project to a spanning tree on the original vertices. For a projected tree copy, the two half-edge stretches sum to ; for another copy, they sum to . In both cases the sum is at least . Hence the average-stretch guarantee on the subdivision implies the inequality used in (45).
We convert this response oracle into a small explicit distribution by multiplicative weights. Start with . At iteration , form
and obtain a response tree from (45) for . It satisfies
Put and update . If , then
The second inequality uses on . Choose a power of two with
Since , the uniform distribution over the response trees has
This is (2). The construction makes polynomial-time average-stretch calls and uses polynomial-time rational arithmetic. A tree is sampled by fair bits.
For a multigraph, retain one cheapest edge per endpoint pair only for tree selection. Its expected-distance bound also applies to every other edge in that bundle, because its cost is no smaller. All original edges remain in the connectivity instance, unless the separate benchmark-preserving reduction of Lemma 6.1 is explicitly used. Zero costs are treated as in Section 3.
A limitation of independent rounding for exact completion
The slack in our connectivity guarantee is essential to the present rounding analysis. The following example explains why exact completion requires more than independent sampling of a feasible fractional augmentation. It concerns one rounding rule on a fixed fractional solution, rather than a lower bound against online algorithms: there is only one request, and its minimum-cost integral augmentation is easy to find.
Proposition B.1. For integers and , there is a simple undirected graph with
and a free base of – connectivity , such that the capacitated cut-LP optimum and the integral augmentation optimum both equal . There is an optimal fractional solution with the following property. If paid edges are selected independently, each with probability at most , where , then
In particular, for , success probability at least a fixed requires . Moreover, if and , the minimum additional cost needed to attain connectivity is at least with probability at least . Both conclusions apply to families with .
Proof. Take internally vertex-disjoint – paths, each consisting of free edges. For every path edge , introduce a private vertex and the detour , where is free and costs one. All free edges are acquired initially. The graph is simple, and counting its path interiors and detour vertices gives the stated size.
Figure 3. A three-stage channel. Solid edges are free; each dashed edge costs one. The construction has channels, each with stages, sharing only and . A channel contributes its second unit of connectivity only after every paid edge on that channel is purchased.
The fractional and integral optima. Set on free edges and on paid edges. Each – cut crosses an original path edge on every channel. The corresponding detour also crosses that cut and contributes at least of fractional capacity, regardless of the shore containing its private vertex. Thus every such cut has -capacity at least . The fractional cost is .
For the reverse inequality, consider the layer cuts: the th cut places every path vertex at depths on the side and those at depths on the side, with each detour vertex on the same side as its preceding path vertex. Its boundary contains exactly free edges and the paid edges of stage . Since each free-edge variable is at most one, every feasible solution of the capacitated cut LP assigns total paid capacity at least one to each layer. The layers use disjoint sets of paid edges, so their constraints imply . Completing all detours on one channel costs and supplies one additional unit of connectivity. Hence both optima equal .
Why independent sampling fails. Each stage of a channel has capacity one until its paid detour edge is purchased, when its capacity becomes two. Since these stages are in series, the channel has connectivity two exactly when all its paid edges have been purchased; otherwise it has connectivity one. Different channels share only their endpoints. Consequently the total connectivity is exactly plus the number of completed channels. Independence bounds the probability of completing any particular channel by ; a union bound proves (46). If and the success probability is at least , then
using and .
The cost of repairing the sample. Let be the number of paid edges selected on channel . The minimum repair cost is exactly , since attaining connectivity requires completing at least one channel. For , each is stochastically dominated by . A Chernoff bound and a union bound give
On the complementary event, every channel needs at least additional paid edges, proving the repair claim. Taking for the first conclusion, or for the second, gives .
In particular, for and , the expected repair cost is at least for all sufficiently large . Thus no universal bound of the form , with fixed , holds for this rounding procedure. The same example applies to independent fundamental-cycle sampling when the spanning tree lies in the free base: selecting a paid fundamental cycle adds exactly its single paid edge. The example leaves open methods that correlate purchases, adapt to failed cuts, or choose a different fractional augmentation.
References
- [1]Anupam Gupta, Ravishankar Krishnaswamy, and R. Ravi. Online and stochastic survivable network design. SIAM Journal on Computing, 41(6):1649–1672, 2012. doi: 10.1137/09076725X. URL https://www.contrib.andrew.cmu.edu/~ravi/sicomp12.pdf. Preliminary version in STOC 2009.DOI
- [2]Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Saeed Seddighin. Greedy algorithms for online survivable network design. In 45th International Colloquium on Automata, Languages, and Programming (ICALP), volume 107 of Leibniz International Proceedings in Informatics, pages 152:1–152:14. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2018. doi: 10.4230/LIPIcs.ICALP.2018.152.DOI
- [3]Mohammad Hajiaghayi. Logarithmic embeddings into probabilistic spanning trees for distances and capacities, 2026. URL https://arxiv.org/abs/2611.05189. arXiv:2611.05189.
- [4]Noga Alon, Richard M. Karp, David Peleg, and Douglas West. A graph-theoretic game and its application to the k-server problem. SIAM Journal on Computing, 24(1):78–100, 1995. doi: 10.1137/S0097539792224474. URL https://dwest.web.illinois.edu/pubs/kserver.pdf.DOI
- [5]Ittai Abraham and Ofer Neiman. Using petal-decompositions to build a low stretch spanning tree. SIAM Journal on Computing, 48(2):227–248, 2019. doi: 10.1137/17M1115575. Preliminary version in STOC 2012.DOI
- [6]Makoto Imase and Bernard M. Waxman. Dynamic Steiner tree problem. SIAM Journal on Discrete Mathematics, 4(3):369–384, 1991. doi: 10.1137/0404033.DOI
- [7]Piotr Berman and Chris Coulston. On-line algorithms for Steiner tree problems (extended abstract). In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC), pages 344–353. ACM, 1997. doi: 10.1145/258533.258618.DOI
- [8]Kamal Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1):39–60, 2001. doi: 10.1007/s004930170004.DOI
- [9]Joseph (Seffi) Naor, Seeun William Umboh, and David P. Williamson. Tight bounds for online weighted tree augmentation. In 46th International Colloquium on Automata, Languages, and Programming (ICALP), volume 132 of Leibniz International Proceedings in Informatics, pages 88:1–88:14. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2019. doi: 10.4230/LIPIcs.ICALP.2019.88.DOI
- [10]Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. The online set cover problem. SIAM Journal on Computing, 39(2):361–370, 2009. doi: 10.1137/060661946. Preliminary version in STOC 2003.DOI
- [11]Niv Buchbinder and Joseph Naor. Online primal-dual algorithms for covering and packing. Mathematics of Operations Research, 34(2):270–286, 2009. doi: 10.1287/moor.1080.0363.DOI
- [12]Sander Borst, Marek Eliáš, and Moritz Venzin. Stronger adversaries grow cheaper forests: Online node-weighted Steiner problems. In Proceedings of the Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 3842–3864. SIAM, 2025. doi: 10.1137/1.9781611978322.129. URL https://arxiv.org/abs/2410.18542.
- [13]Mohit Garg and Aditya Subramanian. Online connectivity augmentation. In Proceedings of the Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 85–104. SIAM, 2026. doi: 10.1137/1.9781611978971.4.DOI
- [14]Mohit Garg, Felix Hommelsheim, and Alexander Lindermayr. Optimal online weighted connectivity augmentation, 2026. URL https://arxiv.org/abs/2610.42046. arXiv:2610.42046.
- [15]Daniel Hathcock, Aditya Subramanian, Seeun William Umboh, and Michael Zlatín. Weighted and unweighted online connectivity augmentation via geometric hitting set, 2026. URL https://arxiv.org/abs/2611.08570. arXiv:2611.08570.
- [16]Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences, 69(3):485–497, 2004. doi: 10.1016/j.jcss.2004.04.011. Preliminary version in STOC 2003.DOI
