Flipping Matchings is Hard
By: Carla Binucci , Fabrizio Montecchiani , Daniel Perz and more
Potential Business Impact:
Finding the fewest steps to change one dot pattern to another is hard.
Given a point set $\mathcal{P}$ and a plane perfect matching $\mathcal{M}$ on $\mathcal{P}$, a flip is an operation that replaces two edges of $\mathcal{M}$ such that another plane perfect matching on $\mathcal{P}$ is obtained. Given two plane perfect matchings on $\mathcal{P}$, we show that it is NP-hard to minimize the number of flips that are needed to transform one matching into the other.
Similar Papers
Flipping odd matchings in geometric and combinatorial settings
Computational Geometry
Lets you change one matching to another.
Constrained Flips in Plane Spanning Trees
Computational Geometry
Makes computer drawings connect without crossing lines.
A Linear Time Algorithm for Finding Minimum Flip Sequences between Plane Spanning Paths in Convex Point Sets
Computational Geometry
Finds shortest way to rearrange points.