I was wondering if there is a better solution for this situation: I have two groups of objects GroupA(A) and GroupB(B), the objects of group A are connected to 2 and only 2 elements in group B, and a object A1 from group A can connect to the same objects that an object A2 connects to. My problem is that i have to find the smallest set of objects of GroupA so that i can reach all objects in GroupB. Currently, i'm trying every option possible and choosing the smallest set that works, but I refuse to believe that is the only solution.

this is my first post so srry if i was not clear enough

CodePudding user response：

This is a variation of the set covering problem. Trying every option is going to be very slow for large sets, but it is the only way to get an optimal solution. If you can settle for a pretty-good (but not optimal) solution, then you can use a greedy algorithm to approximate a solution.

The basic idea is to loop through your GroupA objects and select those that are connected to the most GroupB objects that you haven't covered yet. Keep doing this until you have a set that covers all of GroupB.

CodePudding user response：

Since each object in group A connects to two objects in group B, then you can think of the problem as a graph -- the group A objects are edges, and the group B objects are nodes.

Your problem is then to find a minimum edge cover: https://en.wikipedia.org/wiki/Edge_cover

Thankfully there are polynomial time solutions. The simplest one is to use the Blossom algorithm to find a maximum matching, and then to choose arbitrary edges for the vertices that aren't covered.

Each edge (B object) in the maximum matching covers 2 distinct A objects, and the remaining edges (B objects) cover one new A object each.