First of all, thank you for your time to reading my post.

I am a researcher but not a mathematician, i have some difficulties in solving a math problem, that why i am here to ask your help. I just want your guide/advice cause i have read many algorithms but it seem do not related my problem.

Sorry for any inconvenience cause this is the first time i have ever posted in this site, so in case of mistakes please forgive me and redirect me.

My problem is shown in the attached image (unfortunately i do'nt have credit to attach it), I have an undirected bipartite graph G={V,E} V1={1,2,3,4,5,6} , V2={A,B,C,D} , E={1A,1B,2A,2B,2C,3A,3C,4A,4B,4D,5A,5B,6A,6D} and i want to find the minimum number of vertices from V1 which covers/connects all the vertices of V2. Such that: 1- Each vertex from V1 could cover multi-vertices of V2 (not a single match) 2- The vertex from V1 which has maximum edges toward V2 will be selected first, in case of many option pick the vertex which has the lower id 3- All the vertices in V2 should be covered

so for the given example the minimum set will be {2,4}

Is there any algorithm or theorem does that?

I need your help guys cause i have stuck in this.

Thank you. Retta


This is called the "set cover" problem


It is NP-Hard, though if you need to solve actual instances it can be done with Linear Programming, for instance. You can write that with 5-6 lines of Sage.

| cite | improve this answer | |
  • $\begingroup$ I have updated my question with extra details, may i ask your help cause your suggestion seems does not match my case. $\endgroup$ – user3592519 Jun 18 '14 at 13:41
  • $\begingroup$ "You can write that with 5-6 lines of Sage", could you please give extra details $\endgroup$ – user3592519 Jun 19 '14 at 14:33
  • $\begingroup$ steinertriples.fr/ncohen/tut/LP_examples $\endgroup$ – Nathann Cohen Feb 24 '15 at 9:32

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