Problem of the month May 2010

We extend the problem of the month status of Destroying rigidity to May, in hope of stimulating some more activity on this important problem. The question is the following:

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?

Another way to formulate the question is: can we find in polynomial time a minimum cut of the rigidity matroid of a graph, or more generally, of a count matroid on a hypergraph? In some sense, the 2-dimensional rigidity matroid is the simplest case that is not known.

Please visit the discussion page of the problem if you have any observations, ideas or questions!