Changes

The problem is NP-complete. A related problem was shown to be NP-complete by {{ColourA|Dasgupta, Jiang, Kannan, Li, and Sweedyk}} <ref>B. Dasgupta, T. Jiang, S. Kannan, M. Li, E Sweedyk, ''On the complexity and approximation of syntenic distance'', Discrete Applied Mathematics 88 (1998), 59-82, [http://dx.doi.org/10.1016/S0166-218X(98)00066-3 DOI link] [http://www.cs.uic.edu/~dasgupta/resume/publ/papers/syn4.final.pdf Author link].</ref>: given a bipartite graph ''G'' and an integer ''k'', decide if ''G'' has an induced subgraph on ''2k'' nodes that can be extended to be uniquely matchable. It was observed by {{ColourA|Stéphane Vialette}} that this reduces to the present problem if we add ''n-k'' isolated nodes to both classes.