Strong connectivity augmentation is a computational problem in the mathematical study of graph algorithms, in which the input is a

directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pai ...

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 . They showed that a weighted version of the problem is NP-complete, but the unweighted problem can be solved in

linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...

. Subsequent research has considered the

approximation ratio An approximation is anything that is intentionally similar but not exactly equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix '' ...

and

parameterized complexity In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. ...

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 Condensation is the change of the state of matter from the gas phase into the liquid phase, and is the reverse of vaporization. The word most often refers to the water cycle. It can also be defined as the change in the state of water vapor ...

of the given directed graph, a

directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one v ...

that has one vertex per

strongly connected component In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that ...

of the given graph. Letting

s

denote the number of source vertices in the condensation (strongly connected components with at least one outgoing edge but no incoming edges),

t

denote the number of sink vertices in the condensation (strongly connected components with incoming but no outgoing edges), and

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)

. This follows because

s+q

edges need to be added to provide an incoming edge for each source or isolated vertex, and symmetrically at least

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)

edges to add to the graph to make it strongly connected. Their algorithm uses a

depth-first search Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible alo ...

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)

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 In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...

with

2 was provided by . A parameterized and weighted version of the problem, in which one must add at most

k

edges of minimum total weight to make the given graph strongly connected, is

fixed-parameter tractable In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. ...

Bipartite version and grid bracing application

If a square grid is made of rigid rods (the edges of the grid) connected to each other by flexible joints at the edges of the grid, then the overall structure can bend in many ways rather than remaining square. The

grid bracing In the mathematics of structural rigidity, grid bracing is a problem of adding cross bracing to a square grid to make it into a rigid structure. It can be solved optimally by translating it into a problem in graph theory on the connectivity of b ...

problem asks how to stabilize such a structure by adding additional cross bracing within some of its squares. This problem can be modeled using graph theory, by making a

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...

with a vertex for each row or column of squares in the grid, and an edge between two of these vertices when a square in a given row and column is cross-braced. If the cross-bracing within each square makes that completely rigid, then this graph is undirected, and represents a rigid structure if and only if it is a

connected graph In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgra ...

. However, if squares are only partially braced (for instance by connecting two opposite corners by a string or wire that prevents expansive motion but does not prevent contractive motion), then the graph is directed, and represents a rigid structure if and only if it is a strongly connected graph. An associated strong connectivity augmentation problem asks how to add more partial bracing to a grid that already has partial bracing in some of its squares. The existing partial bracing can be represented as a directed graph, and the additional partial bracing to be added should form a strong connectivity augmentation of that graph. In order to be able to translate a solution to the strong connectivity augmentation problem back to a solution of the original bracing problem, an extra restriction is required: each added edge must respect the bipartition of the original graph, and only connect row vertices with column vertices rather than attempting to connect rows to rows or columns to columns. This restricted version of the strong connectivity augmentation problem can again be solved in linear time.

References

{{reflist, refs= {{citation , last1 = Baglivo , first1 = Jenny A. , author1-link = Jenny Baglivo , last2 = Graver , first2 = Jack E. , contribution = 3.10 Bracing structures , isbn = 9780521297844 , pages = 76–88 , publisher = Cambridge University Press , series = Cambridge Urban and Architectural Studies , title = Incidence and Symmetry in Design and Architecture , title-link = Incidence and Symmetry in Design and Architecture , year = 1983 {{citation , last1 = Eswaran , first1 = Kapali P. , last2 = Tarjan , first2 = R. Endre , author2-link = Robert Tarjan , doi = 10.1137/0205044 , issue = 4 , journal =

SIAM Journal on Computing The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation is ...

, mr = 449011 , pages = 653–665 , title = Augmentation problems , volume = 5 , year = 1976 {{citation , last1 = Frederickson , first1 = Greg N. , last2 = Ja'Ja' , first2 = Joseph , doi = 10.1137/0210019 , issue = 2 , journal =

, mr = 615218 , pages = 270–283 , title = Approximation algorithms for several graph augmentation problems , volume = 10 , year = 1981 {{citation , last = Graver , first = Jack E. , contribution = 2.6 The solution to the grid problem , isbn = 0-88385-331-0 , mr = 1843781 , pages = 50–55 , publisher = Mathematical Association of America , location = Washington, DC , series = The Dolciani Mathematical Expositions , title = Counting on Frameworks: Mathematics to Aid the Design of Rigid Structures , title-link = Counting on Frameworks , volume = 25 , year = 2001 {{citation , last1 = Gabow , first1 = Harold N. , author1-link = Harold N. Gabow , last2 = Jordán , first2 = Tibor , doi = 10.1137/S0097539798347189 , issue = 2 , journal =

, mr = 1769375 , pages = 649–680 , title = How to make a square grid framework with cables rigid , volume = 30 , year = 2000 {{citation , last1 = Klinkby , first1 = Kristine Vitting , last2 = Misra , first2 = Pranabendu , last3 = Saurabh , first3 = Saket , contribution = Strong connectivity augmentation is FPT , date = January 2021 , doi = 10.1137/1.9781611976465.15 , pages = 219–234 , publisher = Society for Industrial and Applied Mathematics , title = Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), doi-access = free {{citation , last = Raghavan , first = S. , editor1-last = Golden , editor1-first = Bruce , editor2-last = Raghavan , editor2-first = S. , editor3-last = Wasil , editor3-first = Edward , contribution = A note on Eswaran and Tarjan's algorithm for the strong connectivity augmentation problem , doi = 10.1007/0-387-23529-9_2 , pages = 19–26 , publisher = Springer , series = Operations Research/Computer Science Interfaces Series , title = The Next Wave in Computing, Optimization, and Decision Technologies , volume = 29 , year = 2005 Computational problems in graph theory Graph connectivity Directed graphs