Sparse Graphs and an Augmentation Problem

For two integers k > 0 and l, a graph G = (V, E) is called (k, l)-tight if vertical bar E vertical bar = k vertical bar V vertical bar - l and vertical bar E(X)vertical bar <= k vertical bar X vertical bar - l for all X subset of V for which k vertical bar X vertical bar - l >= 0. G is called (k, l)-redundant if G - e has a spanning (k, f)-tight subgraph for all e is an element of E. We consider the following augmentation problem. Given a graph G = (V, E) that has a (k, l)-tight spanning subgraph, find a graph H = (V, F) with minimum number of edges, such that G + H is (k, l)-redundant. In this paper, we give a polynomial algorithm and a min-max theorem for this augmentation problem when the input is (k, l)-tight. For general inputs, we give a polynomial algorithm when k >= l and show the NP-hardness of the problem when k < l. Since (k, l)-tight graphs play an important role in rigidity theory, these algorithms can be used to make several types of rigid frameworks redundantly rigid by adding a smallest set of new bars.