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
