Dureza do número cromático fracionário aproximado em gráficos de graus delimitados

Respostas:

11

Sim.

Se entendi corretamente, a prova do Teorema 1.6 em Khot (2001) estabelece que é difícil para NP distinguir entre os dois casos a seguir, mesmo se focarmos em gráficos de grau limitado de grau suficientemente alto:

  1. Há uma cor .k
  2. A proporção do número de vértices para o tamanho máximo de um conjunto independente é pelo menos .klog(k)/25

Da perspectiva do número cromático fracionário, esses dois casos são:

  1. O número cromático fracionário é no máximo .k
  2. O número cromático fracionário é pelo menos .klog(k)/25

Agora devemos lembrar que precisamos de graus suficientemente altos (em função de ). Mas, tanto quanto posso ver, a prova possui, por exemplo, o seguinte corolário conveniente que já pode ser suficiente para seus propósitos:k

  • Dada qualquer constante , existem constantes Δ e c de modo que o seguinte problema em NP-rígido: dado um gráfico G de grau máximo Δ , decida se o número cromático fracionário de G é no máximo c ou pelo menos α c .αΔcGΔGcαc

É claro que isso já implica que não existe PTAS, a menos que P = NP.

Jukka Suomela
fonte
Certamente o último corolário tem alguns outros modificadores sobre as constantes, caso contrário, este é muito bem conhecido para pequenos valores de , c 1 e c 2 ...Δc1 1c2
Andrew D. rei
@ AndrewD.King: Certo, você pode tornar qualquer um deles arbitrariamente grande, etc. Mas talvez você possa postar uma resposta que mostre que a versão simples do corolário pode ser derivada usando técnicas mais antigas e fáceis - acho que já seria suficiente para responder à pergunta do OP?
Jukka Suomela
kΔc1 1c2kc1 1<c2
@ AndrewD.King: Sim, vou editar a resposta; espero que faça mais sentido dessa maneira. :)
Jukka Suomela