Destroying rigidity

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple graph with $n\ge2$. For a placement $p:V\to\mathbb R^2$, its rigidity matrix $R_2(G,p)$ has one row per edge $uv$: the two columns of $u$ contain $p(u)-p(v)$, those of $v$ contain $p(v)-p(u)$, and all other entries vanish. A placement is generic if its coordinates are algebraically independent over $\mathbb Q$. The generic matrix rank depends only on the graph.

Assume $G$ is generically rigid in the plane, meaning $\operatorname{rank}R_2(G,p)=2n-3$ for generic $p$. Define \[ b_2(G)=\min\{|F|:F\subseteq E,\quad \operatorname{rank}R_2(G-F,p)<2n-3\}. \] Can one find $b_2(G)$ and an attaining set $F$ in deterministic polynomial time?

Every deletion retains the full original vertex set. Thus isolating a vertex can destroy rigidity, and no subsequent removal of isolated vertices is implicit. The objective is cardinality; arbitrary edge deletion costs would define a weighted extension. Testing whether a specified deletion succeeds is different from finding the smallest successful deletion among all choices. The property at issue is generic infinitesimal rigidity, not global uniqueness of every realization, nor rigidity at a nongeneric placement with special coordinates.

Short English statement

Can one efficiently find the fewest edges whose removal destroys a graph's generic rigidity in the plane?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000029 (AMR-029-0029), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Destroying rigidity. Original source indexed by AMR-029-0029. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Destroying rigidity. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Destroying_rigidity.