1
$\begingroup$

enter image description here

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

$\endgroup$
  • $\begingroup$ Well, technically speaking, there is always an algorithm to solve a particular case. :) It's a bit like asking for an algorithm to factor 42. $\endgroup$ – Thomas Andrews Jun 18 '14 at 15:35
  • $\begingroup$ You seem to have completely specified the algorithm to be used. $\endgroup$ – Eric Towers Jun 18 '14 at 15:36
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your response, could you please give me extra details or explanation cause i am not expert in math. $\endgroup$ – user3592519 Jun 19 '14 at 16:19
  • $\begingroup$ @user3592519: I can't guess what your background is, so I have added obvious links to the potentially unfamiliar subjects above. $\endgroup$ – Eric Towers Jun 19 '14 at 16:58
  • $\begingroup$ Is the "vertex cover in hypergraphs" is matching my case, it seems a little bit different, i don't to be rude but i really appreciate your advice. May I apply the "vertex cover in hypergraphs" on my bipartite graph with its special requirements?!! $\endgroup$ – user3592519 Jun 19 '14 at 18:14
  • $\begingroup$ The algorithm you give at the end of your post is the 3-approximation algorithm for the vertex cover in hypergraphs. It'll work (as in, will find a cover) but it may include up to 3-times as many vertices in V1 (i.e., hyperedges) as are needed for an optimal cover. $\endgroup$ – Eric Towers Jun 20 '14 at 3:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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