# Destroying rigidity

Let *G* be a graph that is rigid in two-dimensional space. Can we determine in polynomial time the minimum number of edges whose deletion from *G* results in a graph which is not rigid?

## Remarks

The problem can be formulated in matroid terms as it is equivalent to finding a minimum cardinality cut of the 2-dimensional rigidity matroid of *G*. Rigidity matroids are special instances of a more general matroid construction, called count matroids ^{[1]} ^{[2]}, hence the problem is a special case of finding a minimum cut of a count matroid. Several decision and optimization problems can be solved more efficiently in count matroids than in general matroids (see for example ^{[3]}), so it is conceivable that a minimum cut can be found in polynomial time.

It is known that finding the minimum *cycle* of a transversal matroid (a special count matroid) is NP-hard ^{[4]}, but the minimum cut of a transversal matroid can be found in polynomial time.
Geelen, Gerards, and Whittle ^{[5]} conjecture that for any minor-closed class of binary matroids, there is a polynomial-time algorithm for computing the girth (minimum cycle). Geelen and Kapadia ^{[6]} gave a randomized poynomial-time algorithm for computing the girth and the minimum cut of a constant-rank binary perturbation of a graphic matroid. The algorithm is related to the randomized algorithm for the exact matching problem.

See the discussion page for comments and new developments!

## References

- ↑ N. L. White,
*A pruning theorem for linear count matroids*, Congr. Numer. 54 (1986), 259-264. - ↑ W. Whiteley,
*Some matroids from discrete applied geometry*, in Contemporary Mathematics, J. G. Oxley, J. E. Bonin and B. Servatius, Eds., vol. 197. American Mathematical Society, 1996, ResearchGate link - ↑ A Lee, I Streinu,
*Pebble game algorithms and sparse graphs*, Discrete Mathematics 308 (2008), 1425-1437. DOI link, arXiv link. - ↑ S.T. McCormick,
*A Combinatorial Approach to Some Sparse Matrix Problems*, Ph.D. Thesis, Stanford University, Stanford CA (1983), pdf link - ↑ J. Geelen, B. Gerards, and G. Whittle,
*The highly-connected matroids in minor-closed classes*, DOI link, arXiv link - ↑ J. Geelen, R. Kapadia,
*Computing girth and cogirth in perturbed graphic matroids*, arXiv link