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?

Improve this question
$\endgroup$
14
  • 4
    $\begingroup$ I think this is an excellent question for this site; let's hope that someone has a good answer. $\endgroup$
    – Jukka Suomela
    Commented Oct 19, 2011 at 13:57
  • 2
    $\begingroup$ @TysonWilliams: I think the question is perfectly clear. Forget the comment, re-read the question. :) $\endgroup$
    – Jukka Suomela
    Commented Oct 19, 2011 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
    Commented Oct 19, 2011 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
    Commented Oct 19, 2011 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
    Commented Oct 21, 2011 at 12:08

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Oct 19, 2011 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

Improve this answer
$\endgroup$
1
  • 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
    Commented Oct 19, 2011 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.