I don't know much about graph theory so I would need to know if the following problem has a positive answer or a reference. There is an undirected bipartite graph G with the two vertex sets V1, V2.
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}
Is there a function/algorithm that finds the minimum number of vertices from V1 which covers/connects all the vertices of V2 Such that:
- Each vertex from V1 could cover multi-vertices of V2 (not a single match)
- 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
- Each vertex of V2 is connected with at least one vertex of V1
Many thanks
Retta
Best Answer
This is also called the "vertex cover in hypergraphs". Each vertex in $V_2$ is a vertex in the hypergraph. Each vertex in $V_1$ represents an edge in the hypergraph (joining all of its neighbors in $V_2$ using a single hyperedge). This is an NP-hard problem although there are $d$-approximation algorithms where $d$ is the maximum of the degree of the hyperedges (i.e., the degree of the largest vertex in $V_1$). This means if $d=3$, as it is in your given problem instance, there is an algorithm that picks out less than 3-times too many vertices in $V_1$, which is not impressive.