Find dominating set of vertices on one side of bipartite graph

Question

I have a bipartite graph like the one here

I'm trying to find the minimal set of nodes on the right side of the graph such that every node in the left side of the graph is connected to exactly one node on the right side of the graph. For the above graph that would look like this.

I'm not quite sure how I could go about doing this. I have a feeling it's similar to some common problem in graph theory or in basic CS, and that with some transformation becomes equivalent to a problem with a known solution.

Answer 1

"every node in the left side of the graph is connected to exactly one node on the right side of the graph" This sounds like an exact cover problem, which adds packing constraints to set cover. It's also NP-hard, and I'm less optimistic about integer programming for exact cover than for set cover, though it's worth a try. Knuth's Algorithm X probably works better on exact cover than set cover, so it's worth a try as well.

Answer 2

Your problem is NP-hard, as the set cover problem (or rather, the exact cover problem, as David noted) can be reduced to it. One simple exponential-time algorithm works with dynamic programming on subsets of nodes. It can be implemented in time O(2^m * n) where m is the number of nodes on the left side and n is the number of nodes on the right side.

Algorithms based on Branch & Bound are probably more effective in practice.