The strong connectivity augmentation problem was formulated by Kapali Eswaran and Robert Tarjan (1976).
[1] Subsequent research has considered the approximation ratio and parameterized complexity of the weighted problem.
[2][3] 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.
denote the number of sink vertices in the condensation (strongly connected components with incoming but no outgoing edges), and
[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] A minor error in the part of their algorithm that finds the pairs of sources and sinks was later found and corrected.
edges of minimum total weight to make the given graph strongly connected, is fixed-parameter tractable.
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.
[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.
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.