From: gwoegi@fmatbds01.tu-graz.ac.REMOVE.at (Gerhard J. Woeginger) Subject: Re: What is this called? Date: Fri, 25 Feb 2000 11:03:22 Newsgroups: sci.math.research Summary: [missing] In article Marcus Hum writes: >From: Marcus Hum >Subject: What is this called? >Date: Thu, 24 Feb 2000 22:10:18 GMT >Let G = (V, E) be a hypergraph. We would like to find a subset W of V such >that the the intersection of each hyperedge with W has cardinality exactly >one. >Are there known algorithms for finding such a set in a general hypergraph? >Are there known necessary or sufficient conditions on a hypergraph to >ensure the existence of such a set? >Is anyone familiar with this problem? >If G is a graph, we see that such a subset is an stable set which is also >a vertex cover. Notice the similarities to Berge's definition of the >kernel of a graph. In any case, it is an easy exercise to show that G >possesses such a subset iff G is two-colourable. It is well-known that >a two-colouring of a graph is easy to find. >M. Hum There is a polynomial time algorithm for 2-uniform hypergraphs, but the problem becomes NP-complete for 3-uniform hypergraphs: This is essentially problem [LO04] in Garey and Johnson, ONE-IN-THREE-SAT with unnegated literals. - Gerhard ___________________________________________________________ Gerhard J. Woeginger (gwoegi@opt.math.tu-graz.ac.at)