  We first introduce the percolation problems associated with the graph
theoretical concepts of $(k,l)$-sparsity, and make contact with the physical
concepts of ordinary and rigidity percolation. We then devise a renormalization
transformation for $(k,l)$-percolation problems, and investigate its domain of
validity. In particular, we show that it allows an exact solution of
$(k,l)$-percolation problems on hierarchical graphs, for $k\leq l<2k$. We
introduce and solve by renormalization such a model, which has the interesting
feature of showing both ordinary percolation and rigidity percolation phase
transitions, depending on the values of the parameters.
