Efficient algorithm for near-optimal edge-colourings of hypergraphs

Question

Graph colouring problems are, already, hard enough for most people. Even so, I'm going to have to be difficult and ask a problem about hypergraph colouring.

Question.

What efficient algorithms are there for finding an approximately-optimal edge-colouring for k-uniform hypergraphs?

Details ---

• A k-uniform hypergraph is one in which each edge contains precisely k vertices; the usual case of a simple graph is k=2. More precisely, I'm interested in labelled k-uniform hypergraphs, in which two edges may actually have the same vertex-set; but I'll settle for something on k-regular hypergraphs with edges intersecting at no more than k−1 vertices.

• An edge-colouring of hypergraphs is one in which edges of the same colour do not intersect, as with the case of graphs. The chromatic index χ'(H) is the minumum number of colours required, as usual.

• I would like results on deterministic or randomized polynomial time algorithms.

• I'm looking for the best known approximation-factor/additive-gap between what can be efficiently found, and the actual chromatic index χ'(H) --- or for that matter, the best efficiently-attainable result in terms of parameters such as the maximum vertex degree Δ(H), the size of the hypergraph, etc.

Edit: prompted by Suresh's remarks about hypergraph duals below, I should note that this problem is equivalent to the problem of finding a strong vertex colouring of a k-regular hypergraph: that is, where each vertex belongs to k distinct edges [but the edges may now contain differing numbers of vertices], and we want a vertex colouring such that any two adjacent vertices have different colours. This reformulation also does not seem to have an obvious solution.

Remarks

In the case of graphs, Vizing's Theorem not only guarantees that the edge-chromatic number for a graph G is either Δ(G) or Δ(G)+1, standard proofs of it also give an efficient algorithm for finding a Δ(G)+1-edge-colouring. This result would be good enough for me if I were interested in the case k=2; however, I'm specifically interested in k>2 arbitrary.

There doesn't seem to be any well-known results about bounds on hypergraph-edge-colouring, unless you add restrictions such as every edge intersecting in at most t vertices. But I don't need bounds on χ'(H) itself; just an algorithm which will find a "good enough" edge-colouring. [I also don't want to place any restrictions on my hypergraphs, except for being k-uniform, and perhaps bounds on the maximum vertex-degree, e.g. Δ(H) ≤ f(k) for some f ∈ ω(1).]

[Addendum. I have now asked a related question on MathOverlow about bounds on the chromatic number, constructive or otherwise.]

Answer 1

The answer below breaks your condition that you don't want serious restrictions placed on your hypergraph, but it might be of interest if only as related work.

Your hypergraph (which I'll rename as a range space) has a corresponding dual range space (hypergraph) by interchanging the roles of vertices and edges. Your problem then amounts to coloring the elements of this range space so that a range of cardinality $r$ has $r$ colors. Let's call such a range colorful.

There's been some recent work on such "colorful coloring" problems for geometric range spaces, motivated partly by problems in sensor networks. A standard question that's asked is:

Given a parameter $k$ and range space $S$, determine the function $c_S(k)$ such that a $c_S(k)$ coloring of the elements of S guarantees that each range $r$ of $S$ has $\min(|r|, k)$ colors.

Thus, $c_S(\Delta)$ is the quantity you're looking for (where $\Delta$ is the maximum cardinality of a range).

A related question is to determine $c_\tilde{S}(k)$, where $\tilde{S}$ is the dual range space (in effect, your original hypergraph). One example of the kind of results obtained is that:

For $S$ being the space of halfplanes in $\Re^2$, $c_S(k) \le 3k-2$

A good reference for this body of work is the DCG paper by Aloupsis et al, and the references therein.