Jtdylktuy

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:

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. Each vertex of V2 is connected with at least one vertex of V1

Many thanks

Retta

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.