13
$\begingroup$

I am looking for hardness results on vertex coloring of graphs with bounded degree.

Given a graph $G(V,E)$, we know that for any $\epsilon>0$, it's hard to approximate $\chi(G)$ within a factor of $|V|^{1-\epsilon}$ unless $\textit{NP}=\textit{ZPP}$ [1]. But what if the maximum degree of $G$ is bounded by $d$? Are there any hardness ratios of the form $d^{1-\epsilon}$ (for some $\epsilon$) in this case?

An easier question is: Hardness of approximating the edge-chromatic-number of hypergraphs when their edge size is bounded by $d$. Can we hope for a $d^{1-\epsilon}$ hardness ratio in this case? (say, for any $\epsilon >0$)

Thanks for your attention!

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ you can pad a hard instance with isolated vertices $\endgroup$
    – Sasho Nikolov
    Commented Mar 10, 2013 at 5:02
  • 2
    $\begingroup$ Yes, but if you put a finite bound on the size of the hard instance that you start from, it stops being hard. $\endgroup$
    – David Eppstein
    Commented Mar 10, 2013 at 6:05
  • 1
    $\begingroup$ @Sasho How can isolated vertices help when they increase neither the chromatic number nor the maximum degree? $\endgroup$
    – afshi7n
    Commented Mar 10, 2013 at 6:49
  • 2
    $\begingroup$ @DavidEppstein sure, this padding only proves something if $n$ and $d$ are still polynomially related. OP, that is actually precisely the point. you start with an instance with $d$ vertices (so max degree at most $d$) for which it is hard to approximate $\chi$ to within $d^{1-\epsilon}$. add $n - d$ isolated vertices. $\chi$ stays the same and max degree stays $d$. this is polytime if $N = d^{O(1)}$. so for any integer $k$, there exist instances with max degree $d = n^{1/k}$ for which it is hard to approximate $\chi$ to within $d^{1-\epsilon}$ $\endgroup$
    – Sasho Nikolov
    Commented Mar 10, 2013 at 16:35
  • $\begingroup$ Update: It is NP-hard to approximate $\chi(G)$ within a factor of $|V|^{1-\epsilon}$ without any extra assumptions. $\endgroup$
    – Cyriac Antony
    Commented Feb 25, 2020 at 10:29

4 Answers 4

Reset to default
10
$\begingroup$

As David pointed out, Khot's paper, "Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring", Theorem 1.6, says it is NP-hard to color $K$-colorable graph with $2^{\Omega((\log K)^2)}$ colors for graphs with degree at most $2^{2^{(\log K)^2}}$, for sufficiently large constant $K$. In other words, for graphs of degree $d$, it is hard to color $2^{\sqrt{\log\log d}}$-colorable graph with $\log d$ colors.

To get better degree bound, you can probably use ideas from Trevisan's paper "Non-approximability results for optimization problems on bounded degree instances". The key observation is that the graph produced by the FGLSS reduction is a union of complete bipartite subgraphs, and one can replace each of them with a bipartite disperser which is much sparser. Similar idea used in many result such as Chan http://eccc.hpi-web.de/report/2012/110/, Theorem 1.4 / Appendix D.

I think this should give you something like for $2^{\sqrt{c\log d}}$-colorable graphs of degree bounded by $d$, it is NP-hard to color it with $d^{c}$ colors for some constant $0<c<1$.

The degree bound in the paper Michael mentioned is similar to Khot's, namely exponential of the soundness case. Of course the above sparsification approach also improves this, but probably won't give better constant for your purpose.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for your helpful reply, Sangxia. So, from Khot's paper, we could imply a $2^{\Omega(\log \log d)}$ hardness ratio. I think using the improvement in your paper, we can improve that hardness ratio to $2^{2^{\Omega(\sqrt{\log \log d})}}$. Is that correct? $\endgroup$
    – afshi7n
    Commented Mar 12, 2013 at 1:07
  • $\begingroup$ @afshi7n The parameters are a bit tricky here. Stated in terms of degree, Khot's paper gives $\log d / 2^{\sqrt{\log \log d}}$. My paper gives roughly $\log d / (\log\log d)^3$. We can improve the degree of the graph in the reduction with Trevisan's approach. I believe that gives you $d^c$. BTW all these require a sufficiently large constant $d$. $\endgroup$
    – sangxia
    Commented Mar 12, 2013 at 8:25
  • 1
    $\begingroup$ I see, thanks! I also asked Khot via email, he referred me to this paper siam.org/proceedings/soda/2011/SODA11_124_guruswamiv.pdf which I believe gives the $d^c$ assuming Khot's 2-1 conjecture. $\endgroup$
    – afshi7n
    Commented Mar 12, 2013 at 20:48
9
$\begingroup$

There is an inapproximability result for coloring bounded degree graphs in Khot's FOCS'01 paper, "Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring" — it's probably weaker than you want, but at least it's in the right direction.

He proves that, for a parameter $k$ (assumed to be constant), and for $k$-chromatic graphs with degree $2^{k^{O(\log k)}}$, it is NP-hard to find colorings that use $\exp((\log k)^2/25)$ colors. So in terms of the degree $d$, it is hard to color within an $O(\log d)$ factor, but the same inapproximability ratio is also a superpolynomial function of the chromatic number.

Improve this answer
$\endgroup$
8
  • $\begingroup$ David, thanks for your reply. Yes I had seen their result, but I'm hoping to get a hardness ratio better than $\log d$. I think this might be easier to achieve in the second problem, i.e. approximating the edge chromatic number of hypergraphs.. $\endgroup$
    – afshi7n
    Commented Mar 10, 2013 at 23:05
  • $\begingroup$ Why not ask Khot? $\endgroup$
    – Chandra Chekuri
    Commented Mar 10, 2013 at 23:06
  • 1
    $\begingroup$ @chandra Just sent an email and asked him, thanks for the suggestion! I will update here if I heard back. $\endgroup$
    – afshi7n
    Commented Mar 10, 2013 at 23:32
  • $\begingroup$ Actually, the cited paper by Khot proves a gap between k-colorable and $k^{\log k/25}$-colorable graph (not $\exp((k\log k)/25)$. This has recently been improved by Huang to $2^{k^{1/3}}$ in a paper that will appear in the next STOC. (arxiv.org/abs/1301.5216) $\endgroup$
    – Michael Lampis
    Commented Mar 11, 2013 at 19:00
  • $\begingroup$ Why do you think that $k^{(\log k)/25}$ and $\exp((k\log k)/25)$ represent different quantities? Or am I misinterpreting the ambiguous operator precedence of Khot's formula? $\endgroup$
    – David Eppstein
    Commented Mar 11, 2013 at 19:07
8
$\begingroup$

The best known hardness of approximating the chromatic number of $3$-colorable graphs with bounded maximum degree is due to Venkatesan Guruswami and Sanjeev Khanna, On the Hardness of 4-Coloring a 3-Colorable Graph:

There is a constant $\Delta$ such that given a $3$-colorable graph with maximum degree at most $\Delta$, it is NP-hard to color it using just $4$ colors.

Improve this answer
$\endgroup$
5
$\begingroup$

This result might be helpful:

Emden-Weinert, Hougardy, and Kreuter proved that determining whether a graph with maximum degree $\Delta$ has a coloring using $ k=$$\Delta - \sqrt\Delta +1 $ colors is NP-complete ($k\ge 3$)

T. Emden-Weinert, S. Hougardy, B. Kreuter, Uniquely colourable graphs and the hardness of colouring graphs of large girth, Combin. Probab. Comput. 7 (4) (1998) 375–386

Improve this answer
$\endgroup$

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.