Algorithms reveal how to break structural and network rigidity cheaply
Destroying Rigidity in the Plane
Discrete Mathematics
Summary
The paper looks at how to find the smallest set of edges or points to remove from a network or structure so it loses its stiffness or unique shape. The researchers show that some cases can be solved quickly with algorithms, while others are too hard (NP-hard) to solve efficiently. Their work answers previous open questions about how to measure and break rigidity in two-dimensional networks.
What this means in practice
- •For structural engineers: Identify minimal modifications needed to compromise structure stability under 2D conditions, aiding design of safer, more resilient frameworks.
- •For network security teams: Determine critical network components whose removal disrupts position tracking or localization, useful in safeguarding or attacking localization protocols.
A theory result. No direct application yet.
Authors
Yu Cong, Chao Xu, Yajie Zhao
Abstract
Rigidity and global rigidity are fundamental graph properties in discrete geometry, with applications to structural engineering and network localization. In two dimensions, both admit combinatorial characterizations in terms of the rigidity matroid and graph connectivity. We study the computational complexity of finding minimum-cost sets of edges or vertices whose deletion destroys either property in a finite simple graph. With unit costs, we give deterministic polynomial-time algorithms for edge deletion destroying global rigidity and vertex deletion destroying either property. We prove that edge deletion destroying rigidity is NP-hard and that, with positive integer costs, all four problems are NP-hard. These results resolve, in dimension two, the open questions on recognizing robustness under edge and vertex deletions posed by Jordán and Whiteley (2017), as well as the minimum edge-deletion problem for rigidity recorded in EGRES Open.