Part igraph question, part graph theory question. I have a digraph from a set of origin vertices (warehouses) to destination vertices (customers). A given origin vertex has edges only to a limited number of destination vertices, and each destination vertex has edges from a limited number of origin vertices. I want to find the smallest set of origin vertices where each destination vertex has at least one edge into it. Even better if I can weight the origin vertices to enable a preference of one vertex over another.
How can I implement this in igraph (using R), given that I already have a digraph created?
This answer concerns the graph-theoretical part of the question. Let $O$ be the set of origin vertices, $D$ be the set of destination vertices, and for each $v\in O$ let $N(v)$ be a set of destination vertices to which there is an edge from $O$. Then you are looking for a smallest cover of the set $D$ by members of the family $S=\{N(v):v\in O\}$. Unfortunately, without restrictions on $S$ this is a famous set cover problem. This problem is NP-hard, so it should have no known solving algorithms of polynomial running time. Even its approximation is hard. As I understood, it cannot cannot be approximated in polynomial time to within a factor of $(1-o(1))\cdot \ln |D|$ (which essentially matches the approximation ratio achieved by the greedy algorithm), unless $P=NP$.