<p>Is the graph coloring problem complete for poly-APX under C-reductions
(alternatively, under AP-reductions)? For the graph coloring problem, speaking of a feasible solution means a proper coloring for all vertices of the given graph.</p>

<p>The complexity class poly-APX contains all NP optimization problems that can be
approximated within a factor that is polynomial in the size of the
input. The notion of C-reducibility concerns approximation preserving
reductions, which keep the performance ratio of the feasible solutions
under consideration within a linear factor. For definitions regarding
approximation preserving reducibilities, see <a href="http://lcbb4.epfl.ch/reading/np/guideApproxPreservingReduc.pdf" rel="noreferrer" title="P. Crescenzi: A short guide to approximation preserving reducibilites, CCC &#39;97">P. Crescenzi: A short guide to approximation preserving reducibilites, CCC '97</a>.</p>

<p><strong>EDIT (1.8.2014):</strong>
Somewhat related, I've found in the paper "on syntactic versus computational views of approximability" by Khanna, Motwani, Sudan and Vazirani (SICOMP 28(1):164-191) a remark stating that GRAPH COLORING and MAX CLIQUE are both in poly-APX-PB and interreducible (Remark 6 in that paper). I understand this is meant with respect to E-reducibility defined in that paper. Later, in the sketch of proof of Theorem 6 in that paper, I understand that they imply that MAX CLIQUE is complete for poly-APX-PB under E-reductions. I would also be grateful for a proof that GRAPH COLORING is complete for poly-APX-PB w.r.t. E-reducibility.</p>

CC BY-SA 3.0
2014-07-21T15:26:47.570Z
Somewhat up-to-date optimization results are usually at http://www.nada.kth.se/~viggo/problemlist/ ; Minimum Graph Coloring is at http://www.nada.kth.se/~viggo/wwwcompendium/node15.html
argentpepper
CC BY-SA 3.0
2014-08-01T22:03:23.840Z
argentpepper, Thanks for the hint. But I've checked the compendium before asking the question. Unfortunately it does not give any clues about poly-APX-completeness of graph coloring. By the way, is the webpage with the compendium still maintained?
Hermann Gruber
CC BY-SA 3.0
2014-08-04T18:03:59.990Z
I don't know...
argentpepper
<cc.complexity-theory><approximation-hardness><graph-colouring><open-problem><apx>
Is graph coloring complete for poly-APX?
Hermann Gruber
# Is graph coloring complete for poly-APX?

(Asked by: username_0 on 2014-07-20)

Is the graph coloring problem complete for poly-APX under C-reductions
(alternatively, under AP-reductions)? For the graph coloring problem, speaking of a feasible solution means a proper coloring for all vertices of the given graph.

The complexity class poly-APX contains all NP optimization problems that can be
approximated within a factor that is polynomial in the size of the
input. The notion of C-reducibility concerns approximation preserving
reductions, which keep the performance ratio of the feasible solutions
under consideration within a linear factor. For definitions regarding
approximation preserving reducibilities, see [P. Crescenzi: A short guide to approximation preserving reducibilites, CCC '97](http://lcbb4.epfl.ch/reading/np/guideApproxPreservingReduc.pdf "P. Crescenzi: A short guide to approximation preserving reducibilites, CCC '97").

**EDIT (1.8.2014):**
Somewhat related, I've found in the paper "on syntactic versus computational views of approximability" by Khanna, Motwani, Sudan and Vazirani (SICOMP 28(1):164-191) a remark stating that GRAPH COLORING and MAX CLIQUE are both in poly-APX-PB and interreducible (Remark 6 in that paper). I understand this is meant with respect to E-reducibility defined in that paper. Later, in the sketch of proof of Theorem 6 in that paper, I understand that they imply that MAX CLIQUE is complete for poly-APX-PB under E-reductions. I would also be grateful for a proof that GRAPH COLORING is complete for poly-APX-PB w.r.t. E-reducibility.

**Tags:** cc.complexity-theory, approximation-hardness, graph-colouring, open-problem, apx

> **Comments:**
> **username_1**: Somewhat up-to-date optimization results are usually at http://www.nada.kth.se/~viggo/problemlist/ ; Minimum Graph Coloring is at http://www.nada.kth.se/~viggo/wwwcompendium/node15.html  
> **username_0**: username_1, Thanks for the hint. But I've checked the compendium before asking the question. Unfortunately it does not give any clues about poly-APX-completeness of graph coloring. By the way, is the webpage with the compendium still maintained?  
> **username_1**: I don't know...  

---

## 0 answers

