Math Forum

From: Dan Hoey <haoyuep@aol.com>
Date: Sep 21, 2002 9:38 PM
Subject: Re: Covering number of hypergraph

On 21 Aug 2002, ali saman tosun wrote:

> Can a 24-uniform 146-regular hypergraph with 576 vertices have a
> covering number <= 48 ?  Minimum Vertex Cover of hypergraphs is
> NP-complete and approximation algorithm tells me covering numver
> >=24.  I need answer to above question.  24-uniform means all
> hyperedges have 24 vertices on them.  146 regular means each vertex
> has 146 edges adjacent to it.  Covering number is the minimum number
> of vertices such that all edges have one of the vertices on them.

Yes, but it's easier to show one with covering number exactly 24.
Take the vertex set AuB where |A|=24, |B|=552.  Construct a 23-uniform
146-regular hgraph (B,E).  This easy to do by partitioning B into 24
blocks of 23 elements, then creating 145 variants of that partition,
taking care not to duplicate any blocks.

Now take the hgraph E' = {{A_e} u e : e in E}, where vertices A_e are
taken from A, using each element 146 times.  The hgraph {AuB,E'} is of
the required form, and A is a cover.

The NP-completeness result is not very relevant for finding a hgraph
of a particular type, but rather for finding the cover given a hgraph
that has been designed to make the cover hard to find.  Of course, any
24-u 146-r 576-v hgraph with covering number 24 must be an instance of
the construction I've outlined.  But in most cases you should be able
to find the cover fairly easily by looking for pairs of vertices that
never appear in a hedge.  Elements of the cover appear in at least 23
such pairs, while other elements usually appear in few or none.

Dan Hoey
haoyuep@aol.com