Given collections I (items) and S (slots), where I >= S. And a pairing function that determines whether a slot can accept an item.

Is there an efficient way to find whether a "complete" pairing of items to slots exist, where "complete" means every slot is filled?

(More importantly for my use case... is there a way, other than trying every combination, to determine if no such pairing exists?)

  • $\begingroup$ Hall's Marriage Theorem comes to mind. $\endgroup$ – Reinstate Monica Aug 24 '18 at 16:02
  • $\begingroup$ @Solomonoff'sSecret It does, but that's a very inefficient test as you have exponentially many sets to check. It's much more efficient to just construct a maximum-cardinality matching and see if it covers everything you need to cover, since that can be done in polynomial time. $\endgroup$ – David Richerby Aug 24 '18 at 16:03

Yes. You're just looking for a maximum matching in the bipartite graph where one side is the items, the other side is the slots and there's an edge between an item and each slot it's compatible with.

There are a number of efficient algorithms for this. The standard method taught to CS undergraduates is the augmenting paths algorithm of Hopcroft and Karp.

  • $\begingroup$ Perfect! There's even an existing implementation in the language I'm using. $\endgroup$ – Adam Michael Wood Aug 24 '18 at 16:07
  • $\begingroup$ @AdamMichaelWood Awesome! $\endgroup$ – David Richerby Aug 24 '18 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.