Strong connectivity augmentation

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 KapaliEswaranand 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. ^[1] Subsequent research has considered the approximation ratio and parameterized complexity of the weighted problem. ^{[2] [3]}

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 ${\displaystyle s}$ denote the number of source vertices in the condensation (strongly connected components with at least one outgoing edge but no incoming edges), ${\displaystyle t}$ denote the number of sink vertices in the condensation (strongly connected components with incoming but no outgoing edges), and ${\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 ${\displaystyle \max(s+q,t+q)}$. This follows because ${\displaystyle s+q}$ edges need to be added to provide an incoming edge for each source or isolated vertex, and symmetrically at least ${\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 ${\displaystyle \max(s+q,t+q)}$ edges to add to the graph to make it strongly connected. ^[1]

Their algorithm uses a depth-first search on the condensation to find a collection of pairs of sources and sinks, with the following properties: ^[1]

• 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. ^[4]

Once these pairs have been found, one can obtain a strong connectivity augmentation by adding three sets of edges: ^[1]

• 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 ${\displaystyle \max(s+q,t+q)}$. ^[1]

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. ^[1] An approximation algorithm with approximation ratio 2 was provided by Frederickson & Ja'Ja' (1981). ^[2] A parameterized and weighted version of the problem, in which one must add at most ${\displaystyle k}$ edges of minimum total weight to make the given graph strongly connected, is fixed-parameter tractable. ^[3]

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 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 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. ^[5] 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. ^[6]

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. ^[7]

References

1. Eswaran, Kapali P.; Tarjan, R. Endre (1976), "Augmentation problems", SIAM Journal on Computing , 5 (4): 653–665, doi:10.1137/0205044, MR   0449011
2. Frederickson, Greg N.; Ja'Ja', Joseph (1981), "Approximation algorithms for several graph augmentation problems", SIAM Journal on Computing , 10 (2): 270–283, doi:10.1137/0210019, MR   0615218
3. Klinkby, Kristine Vitting; Misra, Pranabendu; Saurabh, Saket (January 2021), "Strong connectivity augmentation is FPT", Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, pp. 219–234, doi: 10.1137/1.9781611976465.15 , ISBN   978-1-61197-646-5
4. Raghavan, S. (2005), "A note on Eswaran and Tarjan's algorithm for the strong connectivity augmentation problem", in Golden, Bruce; Raghavan, S.; Wasil, Edward (eds.), The Next Wave in Computing, Optimization, and Decision Technologies, Operations Research/Computer Science Interfaces Series, vol. 29, Springer, pp. 19–26, doi:10.1007/0-387-23529-9_2, ISBN   978-0-387-23528-8
5. Graver, Jack E. (2001), "2.6 The solution to the grid problem", Counting on Frameworks: Mathematics to Aid the Design of Rigid Structures, The Dolciani Mathematical Expositions, vol. 25, Washington, DC: Mathematical Association of America, pp. 50–55, ISBN   0-88385-331-0, MR   1843781
6. Baglivo, Jenny A.; Graver, Jack E. (1983), "3.10 Bracing structures", Incidence and Symmetry in Design and Architecture, Cambridge Urban and Architectural Studies, Cambridge University Press, pp. 76–88, ISBN   9780521297844
7. Gabow, Harold N.; Jordán, Tibor (2000), "How to make a square grid framework with cables rigid", SIAM Journal on Computing , 30 (2): 649–680, doi:10.1137/S0097539798347189, MR   1769375