[Math] Minimum vertices set bipartite graph covering-special case

bipartite-graphsgraph theory

I was wondering if anyone here could give me any pointers as to how to solve the following problem.

Let B=(L,R,E) be an undirected bipartite graph, ∀u∈L, ∃ s= {ei(u,wi)} ∈E; i=1,2…..n connect u to wi, where w∈R.

The problem is to find a minimum set K from L covering all R in B, K⊆L , ∑u∈K is minimal.

To clarify what I mean by covering: all vertices of R should should have at least one edge to any u∈K.

My intuition is that it's NP-Hard. If that is the case, any idea of what would be the best way to approximate the result (ie a minimum set K of L covering R)? Such that:

  • Each vertex from L could cover multi-vertices of R
  • The vertex from L which has maximum edges toward R will be selected first
  • Each vertex of R is connected with at least one vertex of L

Edit: Here is an example, consider the following bipartite graph: G={L∪R,E},
L={1,2,3,4,5,6},
R={A,B,C,D} ,
E={1A,1B,2A,2B,2C,3A,3C,4A,4B,4D,5A,5B,6A,6D}

And here is a covering minimum set will be {2,4}

I have read many algorithms and solutions like maximum matching, complete matching, stable marriage, set cover problem, vertex cover in hypergraphs …etc.
Unfortunately no one match my case.

So i am here asking your help guys cause i about to fed up!!! SOS!!
enter image description here

Best Answer

This is just the set cover problem in disguise, to each vertex of $L$ assign the set of vertices of $R$ in its neighborhood. We now have transformed $L$ into a set of subsets of $R$ so now we want to find the set covering with the fewest sets.

It is true, as you suspected that this problem is $NP$ complete, but a lot of research on it exists.

Related Question