Abstract 1 Introduction 2 Statement of Problem 3 Motivation and Related Work 4 Empirical Setup 5 Results 6 Conclusion References

An Empirical Analysis of Approximation Algorithms for the Unweighted Tree Augmentation Problem

Luke Hawranick University of South Carolina, Columbia, SC, USA    Matthew Williamson ORCID Marietta College, OH, USA    Jacob Restanio ORCID West Virginia University, Morgantown, WV, USA    K. Subramani ORCID West Virginia University, Morgantown, WV, USA    Cody Klingler West Virginia University, Morgantown, WV, USA
Abstract

In this paper, we perform an experimental study of approximation algorithms for the unweighted tree augmentation problem (UTAP). Our goal is to establish a baseline performance for several existing approximation algorithms on actual instances rather than worst-case instances. In particular, we are interested in whether the algorithms’ performance in practical instances is consistent with their worst-case guarantee rankings. We are also interested in whether preprocessing times, implementation difficulties, and running times justify the use of an algorithm in practice. We profile and analyze three approximation algorithms from the literature against a simple randomized algorithm. The performance of each algorithm was evaluated using metrics for space usage, running time, and solution quality. We found that the simple randomized algorithm is very competitive with the approximation algorithms and that the algorithms do not necessarily rank according to their theoretical guarantees. The randomized algorithm is easier to implement and understand, using less space than any of the more sophisticated approximation algorithms.

Keywords and phrases:
Graphs, Networks, Tree Augmentation, Approximation Algorithms, Empirical
Funding:
K. Subramani: Supported in part by the National Science Foundation through grant CCF-2525738 and the Defense Advanced Research Projects Agency through grant HR0011-25-2-0027.
Copyright and License:
[Uncaptioned image] © Luke Hawranick, Matthew Williamson, Jacob Restanio, K. Subramani, and Cody Klingler; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Networks → Network algorithms ; Theory of computation → Approximation algorithms analysis ; General and reference → Empirical studies
Supplementary Material:
Software: https://github.com/mdw-research/tree-augmentation
  archived at Software Heritage Logo swh:1:dir:4524776372b8580839d2255df71e9ac3276a8ab0
DOI:
10.4230/LIPIcs.SEA.2026.21
Event:
24th Symposium on Experimental Algorithms (SEA 2026)
Editors:
Martin Aumüller and Irene Finocchi
Series and Publisher:
LIPIcs Logo Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The unweighted Tree Augmentation Problem (UTAP) is a well-studied and fundamental problem in network reliability and graph theory [10, 21, 17, 27]. Consider the network in Figure 3. The network becomes disconnected if any of its connections are removed (Figure 3), leaving it vulnerable to incidental failures or targeted attacks. This issue is particularly critical in fault-tolerant infrastructures such as electrical grids [20], telecommunications systems [2, 5], and transportation networks [19, 29]. To ensure reliability, redundancy is introduced by adding extra connections so that the network remains connected even after a single failure (Figure 3).

However, adding redundancy incurs cost [4]. Therefore, minimizing the number of additional connections required to achieve single fault tolerance is a key goal. A graph is said to be 2-edge-connected if the removal of any single edge does not disconnect it. TAP involves a tree and a set of candidate edges, referred to as links. The objective of TAP is to determine the fewest number of links to add to the tree in order to make the resulting graph 2-edge-connected. For clarity, we distinguish between edges (which belong to the given tree) and links (non-tree edges available for augmentation).

Figure 1: A network
where a single edge failure
disconnects it.
Figure 2: The network in Figure 3 disconnected by the removal of an edge.
Figure 3: A network that is single fault tolerant.

Formally, let T=(V,E) be a tree, where V is the set of vertices and E is the set of edges, and L⊆V×V be a set of candidate links disjoint from E. The objective is to find a subset F⊆L such that the augmented tree (V,E∪F) is 2-edge-connected. The links must be chosen from L and cannot be added arbitrarily. This problem is known as the Tree Augmentation Problem [10]. If the input is a graph instead of a tree, we can compute its 2-edge-connected components in O⁢(|V|+|E|) time [28] and contract each component into a single node, yielding a tree.

We focus on the unweighted variant of the problem, where each link has a unit cost. We can view this variant as finding the minimum number of links to add that makes a tree into a 2-edge-connected graph. This restriction provides a clear baseline for analyzing algorithmic structure and approximation behavior without confounding effects from edge weights. Although weighted variants are also studied, they often depend on specific weight distributions and scaling, which can obscure the underlying algorithmic differences. In this work, we focus exclusively on the unweighted case, and all discussion of weighted TAP is included solely for context and comparison with prior literature.

In this paper, we conduct an experimental study of approximation algorithms for the unweighted TAP. We evaluate three classical algorithms by Frederickson and Ja’Ja’ [15], Nagamochi [25], and Even et al. [11], which are representative of major algorithmic approaches to TAP and remain important foundations for subsequent research. These algorithms were selected because they are theoretically significant, practically implementable, and collectively illustrate the trade-offs between simplicity and performance guarantees.

We also introduce a simple randomized heuristic as our own contribution. While it does not provide a formal approximation bound, it is easy to implement and offers insight into how algorithmic simplicity compares to more theoretically grounded methods. We analyze each algorithm in terms of solution quality, runtime, space usage, and implementation complexity, revealing that practical performance does not always align with theoretical guarantees.

The remainder of this paper is organized as follows. Section 2 formally specifies the problem. Section 3 outlines our motivation for studying TAP and reviews related work. Section 4 describes our experimental setup, and Section 5 presents and discusses the results. Section 6 concludes the paper with a summary and directions for future research.

2 Statement of Problem

In this section, we define TAP as well as the various terms that will be used in the rest of the paper. Recall the definition of the edge-connectivity of a graph.

Definition 1.

A graph G=(V,E) is k-edge-connected if the spanning subgraph G′=(V,E\X) is connected for all X⊆E where |X|<k.

By definition, a tree is 1-edge-connected. Adding links to a graph can only increase its connectivity. The problem, which is the focus of the paper, asks how to increase the connectivity of a tree to 2. We formally state the fundamental optimization problem.

Tree Augmentation Problem
Instance: A tree T=(V,E) and a link set L⊆V×V disjoint from E.

Problem: Find a minimum subset F⊆L such that T=(V,E∪F) is 2-edge-connected.

We assume that the instance is feasible, i.e., the graph (V,E∪L) is 2-edge-connected. Equivalently, every tree edge is covered by at least one link in L. Otherwise, no subset F~⊆L can make the graph 2-edge-connected, and the instance admits no feasible solution.

Figure 4 shows an instance of TAP. A simple lower bound on the optimal solution is the ceiling of half the number of leaves in the tree. Since there are 5 leaves in the example, there must be at least 3 links in the optimal solution. Since our solution contains only 3 links, we know it is also optimal. On any given instance, our link set L might not contain leaf-to-leaf links. Thus, not every instance will have an optimal solution that matches this lower bound.

Figure 4: An instance of TAP (a) and an optimal solution (b). The dashed lines indicate the link set L, and the red lines indicate the selected edges F.

3 Motivation and Related Work

TAP is a fundamental problem in network design motivated by improving fault tolerance [17]. The failure of a single edge can disconnect parts of a network, and TAP seeks the smallest set of additional links that make a tree 2-edge-connected. Each link incurs a cost [4], so the objective is to preserve connectivity with minimal overhead. TAP is a special case of the general connectivity augmentation problem, which asks for the smallest set of links that transforms a k-edge-connected graph into a (k+1)-edge-connected one. When k=1, the input is a tree.

TAP is also related to the survivable network design problem and to finding minimum-sized covers of laminar set families [8, 22]. These problems have applications in communication, energy, and transportation networks where reliability is critical [16, 18].

Tarjan [10] first introduced TAP and other graph augmentation problems. Frederickson and Ja’Ja’ [15] later showed that the weighted version (WTAP) is NP-complete by reduction from 3-dimensional matching and proposed the first 2-approximation algorithm via a reduction to the minimum spanning arborescence problem, where an arborescence is a directed, rooted tree in which there is exactly one directed path from the root to every other vertex. Khuller and Thurimella [21] offered a simpler 2-approximation algorithm for undirected graphs.

Nagamochi [26, 25] improved the approximation factor to (1.875+ϵ) by iteratively augmenting a spanning tree and contracting 2-edge-connected components. Building on this work, Even et al. [11] proposed a 1.5-approximation algorithm that combines greedy contractions and a credit-based analysis. Subsequent simplifications and corrections reaffirmed the 1.5 guarantee [12, 13, 23]. More recent work by Grandoni [17] achieved a 1.458-approximation using decomposition and rewiring techniques, which remains the best known theoretical ratio.

Linear programming (LP) and semidefinite programming (SDP) relaxations have further advanced the field. Cheriyan et al. [8] conjectured an integrality ratio of 43, and Nutov [27] later bounded it by 2815. Adjiashvili [1] developed an LP-based (53+ϵ)-approximation and extended it to WTAP with a (1.96417+ϵ) factor. Fiorini et al. [14] refined this approach using {0,12}–Chvátal–Gomory cuts to reach a (32+ϵ) ratio. Cheriyan and Gao [6, 7] proposed a semidefinite programming relaxation achieving a similar bound.

While recent LP- and SDP-based algorithms achieve the best theoretical guarantees, they are complex and computationally demanding. Classical algorithms such as those by Frederickson and Ja’Ja’ [15], Nagamochi [25], and Even et al. [11] remain important due to their simplicity and practicality. These algorithms represent distinct yet foundational approaches to TAP and form the basis for the comparative analysis in this study.

4 Empirical Setup

In this section, we describe the setup for our experiment. First, we will detail the specifics of our experimental design including the types of trees used as input and how the link sets are generated. We also explain how we check a solution’s validity, give a more in-depth overview of the algorithms being tested, and describe the hardware used for the experiment.

4.1 Experimental Design

To evaluate algorithm performance across a variety of structural configurations, we consider six distinct tree types, summarized in Table 1. These input classes were chosen because they reflect a wide range of graph-theoretic properties relevant to TAP, including pathwidth, degree distribution, and subtree depth. Some of these trees, like stars and paths, represent extreme cases (e.g., high centralization or long diameter), while others, like caterpillars and lobsters, model realistic hierarchical structures often seen in communication networks and distributed systems. The inclusion of uniformly random spanning trees captures more unstructured or irregular topologies and provides a baseline for general performance.

Table 1: Descriptions of Input Classes.
Tree Type Description Example Graph
Path Tree V=[n],
E={(i,i+1)∣i∈[n−1]}
Star Tree V=[n],
E={(i,n)∣i∈[n−1]}
Star-like Tree A union of paths in which each path is adjoined at the same vertex.
Caterpillar Tree A tree where all vertices are within distance 1 of a central path.
Lobster Tree A tree where all vertices are within distance 2 of a central path.
Uniform Spanning Tree A spanning tree selected uniformly at random from the set of all spanning trees on the same vertex set.

Our experiments consist of three phases, each corresponding to a different density of the link set for a problem instance. Let T=(V,E). For each tree type in Table 1, we generate link sets L⊆(V×V)\E by including each potential link independently with probability d∈{0.1,0.5,0.8}, so that d represents the fraction of all possible non-tree edges expected in L. For each density, we generate multiple random instances independently, allowing us to evaluate algorithm performance as link set richness varies from sparse (d=0.1) to highly redundant (d=0.8).

In expectation, this yields |L|=Θ⁢(|V|2), ensuring that instances are sufficiently dense to provide a wide range of augmentation choices. Dense link sets prevent situations where limited link availability forces augmentations to be determined primarily by feasibility rather than algorithmic decisions. If (V,E∪L) is not 2-edge-connected after this procedure, additional edges from (V×V)\(E∪L) are selected uniformly at random until the desired connectivity is achieved.

The performance of each algorithm is tested through an experiment of three repetitions of all combinations of one of six input tree types and a link set with one of three densities. The experiment is performed for input trees of size n=100 and n=1000. During each repetition, each algorithm receives the same tree and link set as inputs. Lastly, for each new experiment repetition, new trees and link sets are generated.

All input trees and augmented graph instances are represented using adjacency lists. This allows efficient iteration over neighbors and direct manipulation of edge sets, which is essential for algorithms relying on graph traversal and edge augmentation. Using a consistent representation across all algorithms ensures fairness in both runtime and memory usage comparisons.

4.2 Checking for Validity of Inputs and Solutions

Checking if a given graph is 2-edge-connected can be done in O⁢(|V|+|E|) time using depth-first search. The algorithm finds bridges in a graph by checking if there is an alternate path in the DFS tree to any ancestor of v from the subtree rooted at v. If no bridges are found, the graph is 2-edge-connected. We use this algorithm to verify 2-edge connectivity of inputs (V,E∪L), and again in the returned solution (V,E∪F), where F is the subset of links selected by an algorithm. In each case, the running time for checking if a graph is 2-edge-connected is O⁢(|V|+|E|+|L|).

4.3 Algorithms Considered

We consider four algorithms in our experiment, each described in Table 2. The three approximation algorithms were selected to represent distinct and well-studied paradigms in the design of approximation algorithms for TAP. These paradigms capture the major directions in the evolution of TAP algorithms and allow us to evaluate how different design principles impact empirical performance. Let ρ⁢(n) denote an algorithm’s approximation ratio.

Table 2: The algorithms implemented, design paradigm, approximation factor, and time complexity.
Algorithm Design Paradigm ρ⁢(n) Time Complexity
Randomized (Algorithm 1) Monte Carlo Greedy Augmentation N/A O⁢(|L|⋅(|V|+|L|+|E|))
Frederickson and Ja’Ja’ [15] Global Combinatorial Optimization 2 O⁢(|V|2)
Nagamochi [25] Iterative Structural Reduction 1.875+ϵ O⁢(|V|12⋅|L∪E|+|V|2)
Even et al. [11] LP/Matching Rounding 1.5+ϵ O⁢(|E|⋅|V|2)

While several recent algorithms achieve improved approximation guarantees, such as the (1.66+ϵ)-approximation by Adjiashvili [1], these approaches rely on solving large linear programs with complex constraint structures (often requiring separation or enumeration procedures) and intricate preprocessing steps such as bundle construction. Implementing these components would introduce substantial overhead and obscure the comparison of core algorithmic ideas, particularly for instances of moderate size. In contrast, the chosen algorithms can be implemented using standard graph primitives (e.g., matchings, contractions, and spanning structures) and executed within reasonable time. This allows us to focus on meaningful empirical comparisons without the results being dominated by implementation complexity.

4.3.1 The Randomized Tree Augmentation Algorithm

In order to benchmark the practical performance of the approximation algorithms, we develop a simple randomized algorithm, given by Algorithm 1. The algorithm first selects a random incident link for each leaf and adds it to the solution set F, ensuring that obvious bridges are covered. Since all instances are assumed feasible, every leaf has at least one incident link in L, ensuring that the algorithm is well-defined. It then repeatedly samples links uniformly at random from L∖F until (V,E∪F) becomes 2-edge-connected. Since the algorithm is randomized and may produce different solutions across runs, we execute it 100 times for each instance and report the best solution obtained.

Algorithm 1 Randomized Tree Augmentation.

Algorithm 1 is intended as a simple baseline for empirical comparison rather than a method with formal theoretical guarantees. While it may be possible to analyze its expected performance, deriving a constant-factor approximation in expectation appears nontrivial. We leave this as an interesting direction for future work, focusing here on practical performance across repeated runs.

We prove two lemmata about the performance of Algorithm 1.

Lemma 2.

The random tree augmentation algorithm runs in time O⁢(|L|⋅(|V|+|L|+|E|)).

Proof.

Inserting a link to the solution takes constant time. At most |L| links are added to F. Once a link is added, connectivity is checked at most once with the algorithm in Section 4.2, which takes O⁢(|V|+|E|+|L|) time. There are at most |L|+|E| links and edges in (V,E∪F) when we search for bridges in every iteration. Therefore, the algorithm runs in O⁢(|L|⋅(|V|+|L|+|E|)) time. ◀

Lemma 3.

The random tree augmentation algorithm uses O⁢(|V|+|L|) space.

Proof.

Checking if a graph is 2-edge-connected uses O⁢(|V|) space with the algorithm in Section 4.2. The only data structure that the random tree augmentation algorithm needs is an auxiliary graph to store the solution. We use an adjacency list data structure, requiring O⁢(|V|+|L|) space, as at most |L| links are added to F. Hence, the total space usage is O⁢(|V|+|L|). ◀

4.3.2 Frederickson and Ja’Ja’ Algorithm

Frederickson and Ja’Ja’ [15] provide the first approximation algorithm for TAP, which they referred to as the bridge-connectivity augmentation problem. The algorithm is a 2-approximation method that employs a minimum-weight arborescence (a directed spanning tree rooted at a single vertex) to obtain an approximate solution. In our implementation, the algorithm is realized using adjacency lists to represent the tree and links, allowing efficient traversal and manipulation of edges while preserving directionality and weights.

The procedure begins by selecting any leaf r of the tree T as the root and orienting all tree edges so that every edge direction ultimately leads toward r. In other words, for each non-root vertex v, the unique tree edge on the path from v to r is directed from v toward its parent, so that the root r has only incoming edges while every other vertex has exactly one outgoing edge. Each link is then replaced by two directed versions in opposite directions to allow traversal either way, with each link assigned weight 1 and each tree edge weight 0.

A minimum-weight arborescence is computed on the resulting directed, weighted graph using Edmonds’ algorithm [9], and the approximate solution to TAP is obtained by taking the undirected versions of the edges in this arborescence and combining them with the edges of the original tree. In practice, this computation is the most time-intensive step, running in O⁢(|E|⋅|V|) time for graphs of the sizes we consider, and the space complexity is dominated by the adjacency list representation, which requires at most O⁢(|V|2) memory. The algorithm’s implementation is straightforward, with no additional data structures or optimizations needed beyond the directed graph representation, making it both practical and efficient for our experimental evaluation.

4.3.3 Nagamochi Algorithm

The algorithm by Nagamochi [25] was the first to achieve an approximation factor better than 2 for TAP. It iteratively simplifies the input tree and constructs an augmentation set F by repeatedly applying maximum matching and identifying specific compositions of the tree that allow certain vertices and edges to be contracted. In some cases, these contracted edges are added to the link set L to contribute to the final augmentation. The Nagamochi algorithm is a (1.875+ϵ)-approximation algorithm that runs in O⁢(|V|1/2⋅|L∪E|+|V|2) time for any fixed constant ϵ>0, and it can be implemented efficiently using standard adjacency lists and arrays to track vertex contractions, subtree structures, and link coverage.

At a high level, the algorithm maintains the tree T and link set L and iteratively reduces T while constructing F. While T contains more than one vertex, reduction operations are applied to simplify specific subtrees, retaining only edges necessary for augmentation. A key concept in this process is a minimally leaf-closed subtree, defined as a subtree in which all leaves of the subtree are either leaves of T or adjacent to vertices outside the subtree. By representing the tree using adjacency lists and maintaining a list of active leaves, the implementation can efficiently identify such subtrees and apply local augmentation operations.

The algorithm selects a minimally leaf-closed subtree T′⊆T. If T′ satisfies a condition that allows efficient coverage, a link set Fa⁢p⁢x⊆L is computed to cover its edges using standard maximum matching routines, and the vertices covered are removed from T and L. Otherwise, the algorithm identifies a “lowest solo edge” g, considers the relevant edges in paths associated with g, and computes a link set F+⊆L to cover these edges. The augmentation set is updated accordingly, with bookkeeping handled through simple arrays and flags to track which vertices and edges remain active. This process repeats until T reduces to a single vertex, yielding a 2-edge-connected augmentation in F. In practice, while the algorithm involves multiple tree contractions and matching computations, the careful use of adjacency lists and efficient maximum matching routines ensures that the procedure remains practical for moderately large instances, with memory usage dominated by the storage of the tree, links, and temporary matching structures.

4.3.4 Algorithm by Even et al.

The algorithm by Even et al. [11] constructs a solution by iteratively identifying specific structures in the tree and link set and gradually contracting the input. The algorithm proceeds in two phases. In the first phase, a greedy procedure selects links to cover leaf-to-leaf pairs or cut edges whenever doing so reduces the number of links needed. This phase can be implemented efficiently by maintaining a list of active leaves and scanning for leaf pairs connected by available links, updating the tree structure as leaves and edges are covered or contracted.

The second phase uses a maximum matching algorithm [24] on a carefully constructed auxiliary graph to handle the remaining uncovered portions of the tree. In this auxiliary graph, vertices correspond to the leaves of the tree, and edges represent feasible links between leaves. A maximum matching in this graph identifies links that optimally cover the remaining leaf pairs. Implementation of this step relies on Edmonds’ blossom algorithm, which has a worst-case running time of O⁢(|E|⋅|V|2), and practical implementations use adjacency lists and arrays to track matched and unmatched vertices efficiently. Finding a non-deficient semi-closed subtree, needed to identify valid link candidates, can be accomplished in O⁢(|V|⋅log⁡|V|) time using a priority queue or balanced search structure to maintain active leaves.

By combining the links selected in both phases, the algorithm ensures that no more than 1.5 times the optimal number of links are used, yielding a (1.5+ϵ)-approximation as formally proven by Kortsarz and Nutov [23]. In practice, while the blossom algorithm dominates the running time, careful data structures for leaf tracking, adjacency representations for the auxiliary graph, and incremental updates during contractions make the algorithm feasible for moderately sized trees, with memory usage primarily determined by the tree, link sets, and auxiliary graph.

4.4 Hardware and Implementation

Each algorithm was implemented in Python 3.10 using the NetworkX library, with its functions employed for deletion, insertion, and merging operations on each graph. Input graphs were generated randomly. NetworkX directly generated paths, stars, and uniform random spanning trees, while random instances of caterpillar, lobster, and starlike trees were implemented manually.

Each algorithm was evaluated on the Regular Memory partition of the Bridges-2 High-Performance Computing (HPC) cluster [3]. The HPC cluster uses AMD EPYC 7742 CPUs with 64 cores capable of running at a base clock speed of 2.25 GHz and a boost clock speed of up to 3.4 GHz. For each execution, a single processor core was assigned, and all computations ran on that core without switching to other processors. Only one thread was used per execution. Bridges-2 schedules tasks using a time-sharing scheme in a queue of user-submitted jobs. Once a task is given priority, it executes to completion or until the maximum allotted time is reached.

5 Results

We now detail the results of our experiments, organized by input tree size. All figures in this section follow a consistent convention. Each plot compares the four algorithms studied (Randomized, Frederickson and Ja’Ja’, Nagamochi, and Even et al.) using boxplots to show the distribution of results across the different tree classes. The x-axis represents the algorithms studied, while the y-axis corresponds to the measured metric (solution size, running time, or memory usage). For each boxplot, the red “X” is the mean, while the red line is the median. This standard visualization scheme is maintained throughout the section so that only key trends and observations need to be discussed for each result.

5.1 Size 100

For trees with n=100 (Figures 5–7), the algorithm by Even et al. consistently produces the smallest solutions. This can be attributed to its sophisticated techniques for identifying valuable links through maximum matchings and greedy contractions. The randomized algorithm also performs well, generally outperforming the Frederickson and Ja’Ja’ algorithm and the Nagamochi algorithm in terms of solution quality. The latter two yield similar results, which is expected since setting ε=0.1 gives Nagamochi’s algorithm an approximation guarantee of 1.975, closely matching the 2-approximation of the Frederickson and Ja’Ja’ algorithm.

Figure 5: Empirical solution quality, varying input tree classes for n=100.

Regarding running time (Figure 6), the Frederickson and Ja’Ja’ algorithm is the fastest due to its simpler structure and avoidance of complex data structures or iterative refinements. The algorithms by Nagamochi and Even et al. are slower but comparable to each other, reflecting their more intricate subroutines. The randomized algorithm is substantially slower, as each of its 100 trials requires verifying 2-edge-connectivity through multiple DFS traversals.

Figure 6: Empirical running times, varying input tree classes for n=100.

In terms of memory usage (Figure 7), the randomized algorithm is the most efficient, requiring minimal storage. The algorithms by Nagamochi and Even et al. use more memory due to their auxiliary data structures, while the Frederickson and Ja’Ja’ algorithm demands the most memory because its reliance on Edmonds’ minimum spanning arborescence algorithm [9] involves deep recursion that increases call stack size.

Figure 7: Empirical memory usage, varying input tree classes for n=100.

5.2 Size 1000

For inputs of size n=1000, the comparative performance among algorithms remains consistent with the trends observed for n=100 (Figures 8–10). As shown in Figure 8, the algorithm by Even et al. continues to produce the smallest solutions, followed by the randomized algorithm, the Frederickson and Ja’Ja’ algorithm, and finally the Nagamochi algorithm.

Figure 8: Empirical solution quality, varying input tree classes for n=1000.

Figure 9 reveals a shift in runtime behavior relative to Figure 6. For larger instances, Nagamochi’s algorithm exhibits the slowest performance due to its exhaustive search for reducible cases, many of which involve small subgraphs that are computationally expensive to identify. Compared to the algorithm by Even et al., it performs a greater number of fine-grained reductions, further increasing its running time. The randomized algorithm is more competitive at this scale, particularly for tree classes where leaves are concentrated around a central vertex or path (e.g., caterpillar, path, star, and lobster trees), suggesting that random link selection can effectively cover such structures.

Figure 9: Empirical running times, varying input tree classes for n=1000.

Finally, Figure 10 shows that memory usage patterns are consistent with those observed for n=100 (Figure 7). The randomized algorithm remains the most memory-efficient, while the Frederickson and Ja’Ja’ algorithm requires substantially more memory due to the recursion depth in Edmonds’ arborescence procedure. The algorithms by Nagamochi and Even et al. fall between these extremes, reflecting their moderate reliance on auxiliary data structures.

Figure 10: Empirical memory usage, varying input tree classes for n=1000.

6 Conclusion

In this paper, we presented an empirical evaluation of approximation algorithms for the Tree Augmentation Problem. Alongside several classical algorithms from the literature, we introduced a simple randomized algorithm and evaluated all methods with respect to solution quality, running time, and space usage on a diverse set of input trees.

Our results show that algorithms with stronger theoretical approximation guarantees do not necessarily yield better practical performance on moderate-sized instances. In particular, the randomized algorithm proved competitive across all metrics, often matching or outperforming more sophisticated approaches while requiring less implementation effort and computational overhead. These findings suggest that algorithmic simplicity and efficiency can be more influential than worst-case guarantees in practical TAP settings.

Future work includes extending this study to additional approximation algorithms, enhancing the randomized approach with greedy heuristics, and conducting a parallel empirical evaluation of weighted TAP.

References

  • [1] David Adjiashvili. Beating approximation factor two for weighted tree augmentation with bounded costs. ACM Trans. Algorithms, 15(2), 2018. doi:10.1145/3182395.
  • [2] Waqar Ahmad, Osman Hasan, Usman Pervez, and Junaid Qadir. Reliability modeling and analysis of communication networks. Journal of Network and Computer Applications, 78:191–215, 2017. doi:10.1016/j.jnca.2016.11.008.
  • [3] S. T. Brown, P. Buitrago, E. Hanna, S. Sanielevici, R. Scibek, and N. A. Nystrom. Bridges-2: A platform for rapidly-evolving and data intensive research. In Practice and Experience in Advanced Research Computing, pages 1–4, 2021. doi:10.1145/3437359.3465593.
  • [4] Keren Censor-Hillel and Michal Dory. Fast distributed approximation for TAP and 2-edge-connectivity. Distributed Comput., 33(2):145–168, 2020. doi:10.1007/S00446-019-00353-3.
  • [5] Shin-Guang Chen. Computation in Network Reliability, pages 107–126. Springer International Publishing, Cham, 2020. doi:10.1007/978-3-030-43412-0_7.
  • [6] Joseph Cheriyan and Zhihan Gao. Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP. Algorithmica, 80(2):530–559, 2018. doi:10.1007/S00453-016-0270-4.
  • [7] Joseph Cheriyan and Zhihan Gao. Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part II. Algorithmica, 80(2):608–651, 2018. doi:10.1007/S00453-017-0275-7.
  • [8] Joseph Cheriyan, Tibor Jordán, and R. Ravi. On 2-Coverings and 2-Packings of Laminar Families. In Jaroslav Nesetril, editor, Algorithms - ESA ’99, 7th Annual European Symposium, Prague, Czech Republic, July 16-18, 1999, Proceedings, volume 1643 of Lecture Notes in Computer Science, pages 510–520. Springer, 1999. doi:10.1007/3-540-48481-7_44.
  • [9] Jack Edmonds. Optimum branchings. National Bureau of Standards, 1967.
  • [10] Kapali P. Eswaran and R. Endre Tarjan. Augmentation problems. SIAM Journal on Computing, 5(4):653–665, 1976. doi:10.1137/0205044.
  • [11] Guy Even, Jon Feldman, Guy Kortsarz, and Zeev Nutov. A 3/2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set (extended abstract). Lecture Notes in Computer Science, October 2001.
  • [12] Guy Even, Jon Feldman, Guy Kortsarz, and Zeev Nutov. A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. ACM Transactions on Algorithms, 5, March 2009. doi:10.1145/1497290.1497297.
  • [13] Guy Even, Guy Kortsarz, and Zeev Nutov. A 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. Inf. Process. Lett., 111(6):296–300, 2011. doi:10.1016/J.IPL.2010.12.010.
  • [14] Samuel Fiorini, Martin Groß, Jochen Könemann, and Laura Sanità. Approximating weighted tree augmentation via chvátal-gomory cuts. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 817–831. SIAM, 2018. doi:10.1137/1.9781611975031.53.
  • [15] Greg N. Frederickson and Joseph Ja’Ja’. Approximation algorithms for several graph augmentation problems. SIAM Journal on Computing, 10(2):270–283, 1981. doi:10.1137/0210019.
  • [16] Michel X. Goemans, Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos, and David P. Williamson. Improved Approximation Algorithms for Network Design Problems. In Daniel Dominic Sleator, editor, Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, Arlington, Virginia, USA, pages 223–232. ACM/SIAM, 1994. URL: http://dl.acm.org/citation.cfm?id=314464.314497.
  • [17] Fabrizio Grandoni, Christos Kalaitzis, and Rico Zenklusen. Improved approximation for tree augmentation: saving by rewiring. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 632–645. ACM, 2018. doi:10.1145/3188745.3188898.
  • [18] Kamal Jain. A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. Comb., 21(1):39–60, 2001. doi:10.1007/S004930170004.
  • [19] Weiwei Jing, Xiangdong Xu, and Yichao Pu. Route redundancy-based approach to identify the critical stations in metro networks: A mean-excess probability measure. Reliability Engineering & System Safety, 204:107204, 2020. doi:10.1016/j.ress.2020.107204.
  • [20] Joel Jose and Anupama Kowli. Optimal augmentation of distribution networks for improved reliability. IEEE Systems Journal, 16(2):1965–1973, 2022. doi:10.1109/JSYST.2021.3089716.
  • [21] Samir Khuller and Ramakrishna Thurimella. Approximation Algorithms for Graph Augmentation. J. Algorithms, 14(2):214–225, 1993. doi:10.1006/JAGM.1993.1010.
  • [22] Guy Kortsarz and Zeev Nutov. Approximating minimum cost connectivity problems. In Parameterized complexity and approximation algorithms, volume 9511 of Dagstuhl Seminar Proceedings (DagSemProc). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2010. doi:10.4230/DagSemProc.09511.4.
  • [23] Guy Kortsarz and Zeev Nutov. A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2. ACM Trans. Algorithms, 12(2):23:1–23:20, 2016. doi:10.1145/2786981.
  • [24] Silvio Micali and Vijay V. Vazirani. An O⁢(|v|⋅|E|) algoithm for finding maximum matching in general graphs. In 21st Annual Symposium on Foundations of Computer Science (sfcs 1980), pages 17–27, 1980.
  • [25] Hiroshi Nagamochi. An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree. Discrete Applied Mathematics, 126(1):83–113, 2003. 5th Annual International Computing and combinatorics Conference. doi:10.1016/S0166-218X(02)00218-4.
  • [26] Hiroshi Nagamochi and Toshihide Ibaraki. An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree. In Takano Asano, Hideki Imai, D. T. Lee, Shin-ichi Nakano, and Takeshi Tokuyama, editors, Computing and Combinatorics, pages 31–40, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg. doi:10.1007/3-540-48686-0_3.
  • [27] Zeev Nutov. On the tree augmentation problem. Algorithmica, 83(2):553–575, 2021. doi:10.1007/S00453-020-00765-9.
  • [28] R. Endre Tarjan. A note on finding the bridges of a graph. Information Processing Letters, 2(6):160–161, April 1974. doi:10.1016/0020-0190(74)90003-9.
  • [29] Xiangdong Xu, Anthony Chen, Guangming Xu, Chao Yang, and William H.K. Lam. Enhancing network resilience by adding redundancy to road networks. Transportation Research Part E: Logistics and Transportation Review, 154:102448, 2021. doi:10.1016/j.tre.2021.102448.