12
$\begingroup$

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.]

$\endgroup$
  • $\begingroup$ It seems that this problem is sometimes called the hypergraph packing. Does the following page help? en.wikipedia.org/wiki/Packing_in_a_hypergraph $\endgroup$ – Tsuyoshi Ito Sep 6 '10 at 21:06
  • $\begingroup$ I am afraid that the Wikipedia article which I linked in the previous comment may not be a good material to learn about the subject; the terminology is confusing, the same notion is apparently defined more than once, and so on. I hope that someone knows a better material. $\endgroup$ – Tsuyoshi Ito Sep 6 '10 at 21:24
  • $\begingroup$ The asker recently posted a closely related question on MathOverflow: mathoverflow.net/questions/38853/…. @Niel de Beaudrap: Next time you repost a question in a different place, please add links in both directions. $\endgroup$ – Tsuyoshi Ito Sep 19 '10 at 20:02
  • $\begingroup$ @Tsuyoshi: Thank you for your continued interest in my problem. I didn't add the link from here to MO because interest in the topic seemed essentially to have died here, without much progress toward what I would consider to be a satisfactory answer. (In any case, I linked back to this question in the MO question; and priority can be easily established by looking at when it was asked.) —— It's not obvious to me why you feel it is important that I link reciprocally, before there are any answers to the question on MO to inform possible answers here; but since you ask, I will do so. $\endgroup$ – Niel de Beaudrap Sep 20 '10 at 5:30
  • $\begingroup$ I will translate my 2 cents from the mathoverflow post back here... the best possible chromatic number for hypergraphs of max degree $\Delta$ and max edge size r is $\Theta(\Delta * r)$, this now appears in a manuscript at arxiv.org/abs/1009.6144 $\endgroup$ – daveagp Oct 1 '10 at 10:55
3
$\begingroup$

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.

$\endgroup$

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.