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, $ \forall u \in L$, let $S:=\{(u,w_i)\in E|w_i \in R\}$(The set of edges incident to $u$). The problem is to find a minimum set $K\subset L$ covering all $R$.
To clarify what I mean by covering: all vertices of $R$ should should have at least one edge connected to some $u \in K$.
My intuition is that it's not $NP-Hard$. But can not find a polynomial time algorithm. 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\cup 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!!
This question was poted in Minimum vertices set bipartite graph covering-special case
The greedy algorithm to approximate solve it is as follows: 1. Chose a vertex $a$ from $L$ which covers "more" nodes left in $R$ (i.e the vertex from $L$ with more edges)
1.1 Add the vertex $a$ the mininum cover set
1.2 Remove all the nodes in $R$ having an edge to $a$
1.3 Remove the vertex $a$ from $L$
2 In case $R$ is not empty, go to point 1
However, this is not the optimal one. Can any one help me?