Problem of the month April 2010

The problem for this month is one of the few questions that remains open in two-dimensional 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?

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? The status of the minimum cut problem is settled for several classes of matroids: it is NP-hard for gammoids and for binary matroids, but it is polynomial for graphic and hypergraphic matroids. A solution for the rigidity matroid would be improtant from a theoretical as well as from a practical point of view.

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