Turns out that it's not the classic Marriage Problem, but rather the Assignment Problem, which is superficially similar but whose algorithm is quite different, at least at first glance. The Assignment Problem's classic algorithm is called the Hungarian Algorithm. If I'm understanding what I'm reading, the full Hungarian Algorithm is N^3, but we only need a part of its cleverness, so I think our case is down to quadratic. Thank you for the clue, which at least got me some search terms. On Tue, Apr 13, 2010 at 5:28 PM, Schroeppel, Richard <rschroe@sandia.gov>wrote:
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 <math-fun-bounces%2Brschroe>=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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun