This looks like the "Marriage Problem". It's polynomial time, N^3 or N^4. The algorithm gives either a solution, or a set of rows (or columns) that, when Ored together, have too few 1s to have a set of matching columns (or rows). This is a constructive, quickly checkable proof, that there's no solution. The algorithm was reprinted in a famous New Yorker spoof, along with one of their wry comments. "Much like in the real world." Counting the number of solutions is #P complete; or requiring that the set of 1s, interpreted as edges of a graph, form (only) one cycle of N edges, is the Hamiltonian Path problem, which is NP-complete. Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com [mailto:math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com] On Behalf Of Allan Wechsler Sent: Tuesday, April 13, 2010 2:50 PM To: math-fun Subject: [math-fun] NP-complete matching problem? 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? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun