16
$\begingroup$

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.

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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Somewhat up-to-date optimization results are usually at nada.kth.se/~viggo/problemlist ; Minimum Graph Coloring is at nada.kth.se/~viggo/wwwcompendium/node15.html $\endgroup$
    – argentpepper
    Jul 21 '14 at 15:26
  • $\begingroup$ 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? $\endgroup$
    – Hermann Gruber
    Aug 1 '14 at 22:03
  • $\begingroup$ I don't know... $\endgroup$
    – argentpepper
    Aug 4 '14 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.