13 Apr
2010
13 Apr
'10
2:50 p.m.
The following problem actually came up in the course of my work. I was pretty sure I'd heard of it before, and that it was NP-complete, but now I can't reconstruct my references, and I'm starting to doubt myself. The problem instance is a square N-by-N matrix of 1's and 0's. A solution consists of a set of N cells, all 1's, with including exactly one from each row and column, or the assertion that no such set exists. Alternatively, the instance is an (N,N)-bipartite graph, and a solution consists of a degree-1 subgraph (a matching) that includes all the vertices, or the assertion that no such matching exists. What is the classic name for this problem? What is its complexity?