In my workplace I have stumbled upon the following problem that I am asked to solve. A solution is preferred although not absolutely required.
There is a database with a set of stories, and each story has a set of topics associated with it. The topics are stored in a separate table of the form (storyid, topicid).
The question is how to select ideally 5 topics (or at least 2, if 5 is impossible) such that each topic has 2 stories (or 1, if 2 is impossible) that are not repeated in any of the other selected topics. The algorithm must also return which exactly are the "proper" stories associated with each topic.
Is this actually an NP-complete problem that has no efficient solution that goes beyond simple enumeration of all possibilities or does it have an efficient solution?
If it does not have an efficient solution, please try to prove it (although not absolutely necessary).
If it does have an efficient solution, please be kind and post it.