Твердость аппроксимации дробного хроматического числа на ограниченных графах степени

10

Сложно ли приблизить приблизительное дробное хроматическое число на графах с ограниченными градусами?

Ашвинкумар Б.В.
источник
Что такое дробное хроматическое число?
Мухаммед Аль-Туркистани
5
@ MohammadAl-Turkistany: LP-репликация хроматического числа, см., Например, en.wikipedia.org/wiki/Fractional_coloring
Юкка Суомела

Ответы:

11

Да.

Если я правильно понял, доказательство теоремы 1.6 в Хоте (2001) устанавливает, что NP-трудно различить следующие два случая, даже если мы сосредоточимся на графах ограниченной степени достаточно высокой степени:

  1. k
  2. klog(k)/25

С точки зрения дробного хроматического числа эти два случая:

  1. k
  2. klog(k)/25

k

  • αΔcGΔGcαc

Конечно, это уже означает, что PTAS отсутствует, если только P = NP.

Юкка Суомела
источник
Δc1c2
@ AndrewD.King: Да, вы можете сделать любой из них произвольно большим и т. Д. Но, возможно, вы могли бы опубликовать ответ, который показывает, что простая версия следствия может быть получена с использованием более старых и простых методов - я думаю, что это уже будет достаточно ответить на вопрос ОП?
Юкка Суомела
kΔc1c2kc1<c2
@ AndrewD.King: Да, я буду редактировать ответ; надеюсь, это будет иметь больше смысла. :)
Юкка Суомела