12
$\begingroup$

In my job the following problem arises:

Is there a known algorithm, that approximates the chromatic number of a graph without an independent set of order 65? (So alpha(G)<=64 is known and |V|/64 is a trivial lower, |V| a trivial upper bound. But are there better proven approximations under this special condition?)

What if we relax to the fractional chromatic number? And to "good" running times in average cases?

$\endgroup$
  • 4
    $\begingroup$ I think this is an excellent question for this site; let's hope that someone has a good answer. $\endgroup$ – Jukka Suomela Oct 19 '11 at 13:57
  • 2
    $\begingroup$ @TysonWilliams: I think the question is perfectly clear. Forget the comment, re-read the question. :) $\endgroup$ – Jukka Suomela Oct 19 '11 at 14:13
  • 6
    $\begingroup$ The funny thing is, this conditions guarantees that the trivial approximation is a 64-approximation to the optimum. I wonder whether just the promise of a small independence number can give a better algorithm. $\endgroup$ – Sasho Nikolov Oct 19 '11 at 16:04
  • 3
    $\begingroup$ Is the problem motivated by practical application? If so, one should focus on interesting heuristics that are going to do well - improving the trivial 64 approximation is not that interesting. $\endgroup$ – Chandra Chekuri Oct 19 '11 at 17:16
  • 2
    $\begingroup$ By the way, if you want to find good approximations of the fractional chromatic number quickly, it is sufficient to find good approximations of max-weight independent sets quickly. Hence this suggest a new question: If we know that the largest independent set has size 64, is there an algorithm that finds good approximations of max-weight independent sets much faster than the trivial $O(n^{64})$-time algorithm? $\endgroup$ – Jukka Suomela Oct 21 '11 at 12:08
12
$\begingroup$

Compute a maximum matching in the complement of the input graph. Every unmatched node must be in a different color class in any coloring. So: if you get at least cn matched edges, then the matching itself gives you a coloring with an upper bound of (1-c)n, and an approximation ratio of 64(1-c). If you don't get at least cn edges, then you get a lower bound of (1 - 2c)n colors and an approximation ratio of 1/(1-2c). Solving the equation 64(1-c) = 1/(1-2c) leads to an approximation ratio slightly larger than 32; see Sasho Nikolov's comment for the precise value.

| cite | improve this answer | |
$\endgroup$
  • 9
    $\begingroup$ small correcion: in the first case the upper bound is (1-c)n and the lower bound is n/64, so the approx ratio is (1-c)64. When you solve (1-c)64 = 1/(1-2c), you get $c = 3/16 (4-\sqrt{2}) \approx 0.5$ and approximation ratio $\approx 32$. Seems like given an upper bound of $k$ for $\alpha(G)$, this method gives an approximation ratio that goes to $\frac{k}{2}$ as $k$ goes to infinity. $\endgroup$ – Sasho Nikolov Oct 19 '11 at 17:01
5
$\begingroup$

You might be interested in the colouring number, which is 1 plus the maximum over all subgraphs $H$, of the minimum degree of $H$. It can be computed efficiently, and is an upper bound for the chromatic number.

http://en.wikipedia.org/wiki/Colouring_number#Algorithms

| cite | improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ Minor correction: it is not true that the coloring number equals the least number of colors in a greedy coloring. If you order the vertices according to their colors in an optimal coloring (with the additional property that the first color class is maximal, and the second is maximal in the remaining graph etc) then the greedy algorithm will find the same optimal coloring. $\endgroup$ – David Eppstein Oct 19 '11 at 19:36

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.