Strong connectivity augmentation is a computational problem in the mathematical study of graph algorithms, in which the input is a directed graph and the goal of the problem is to add a small number of edges, or a set of edges with small total weight, so that the added edges make the graph into a strongly connected graph. The strong connectivity augmentation problem was formulated by Kapali Eswaran and Robert Tarjan (1976). They showed that a weighted version of the problem is NP-complete, but the unweighted problem can be solved in linear time. Subsequent research has considered the approximation ratio and parameterized complexity of the weighted problem.
Unweighted version In the unweighted strong connectivity augmentation problem, the input is a directed graph and the goal is to add as few edges as possible to it to make the result into a strongly connected graph. The algorithm for the unweighted case by Eswaran and Tarjan considers the condensation of the given directed graph, a directed acyclic graph that has one vertex per strongly connected component of the given graph. Letting s {\displaystyle s} denote the number of source vertices in the condensation (strongly connected components with at least one outgoing edge but no incoming edges), t {\displaystyle t} denote the number of sink vertices in the condensation (strongly connected components with incoming but no outgoing edges), and q {\displaystyle q} denote the number of isolated vertices in the condensation (strongly connected components with neither incoming nor outgoing edges), they observe that the number of edges to be added is necessarily at least max ( s + q , t + q ) {\displaystyle \max(s+q,t+q)} . This follows because s + q {\displaystyle s+q} edges need to be added to provide an incoming edge for each source or isolated vertex, and symmetrically at least t + q {\displaystyle t+q} edges need to be added to provide an outgoing edge for each sink or isolated vertex. Their algorithm for the problem finds a set of exactly max ( s + q , t + q ) {\displaystyle \max(s+q,t+q)} edges to add to the graph to make it strongly connected. Their algorithm uses a depth-first search on the condensation to find a collection of pairs of sources and sinks, with the following properties:
The source of each pair can reach the sink of the pair by a path in the given graph. Every source that is not in one of the pairs can reach a sink in one of the pairs. Every sink that is not in one of the pairs can be reached from a source in one of the pairs. A minor error in the part of their algorithm that finds the pairs of sources and sinks was later found and corrected. Once these pairs have been found, one can obtain a strong connectivity augmentation by adding three sets of edges:
The first set of edges connects the pairs and the isolated vertices of the condensation into a single cycle, consisting of one edge per pair or isolated vertex. The second set of edges each connect one of the remaining sinks to one of the remaining sources (chosen arbitrarily). This links both the source and the sink to the cycle of pairs and isolated vertices at a cost of one edge per source-sink pair. Once the previous two sets of edges have either exhausted all sources or exhausted all sinks, the third set of edges links each remaining source or sink to this cycle by adding one more edge per source or sink. The total number of edges in these three sets is max ( s + q , t + q ) {\displaystyle \max(s+q,t+q)} .
Weighted and parameterized version The weighted version of the problem, in which each edge that might be added has a given weight and the goal is to choose a set of added edges of minimum weight that makes the given graph strongly connected, is NP-complete. An approximation algorithm with approximation ratio 2 was provided by Frederickson & Ja'Ja' (1981). A parameterized and weighted version of the problem, in which one must add at most k {\displaystyle k} edges of minimum total weight to make the given graph strongly connected, is fixed-parameter tractable.
… excerpt ends here. Continue reading the full article.
