É extremamente difícil aproximar o número cromático fracionário em gráficos de graus limitados?
cc.complexity-theory
graph-theory
approximation-hardness
graph-colouring
bounded-degree
Ashwinkumar BV
fonte
fonte
Respostas:
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:
Da perspectiva do número cromático fracionário, esses dois casos são:
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
É claro que isso já implica que não existe PTAS, a menos que P = NP.
fonte