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

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

cc.complexity-theory graph-theory approximation-hardness graph-colouring bounded-degree Ашвинкумар Б.В.
источник

Что такое дробное хроматическое число?

Мухаммед Аль-Туркистани

@ MohammadAl-Turkistany: LP-репликация хроматического числа, см., Например, en.wikipedia.org/wiki/Fractional_coloring

Юкка Суомела

Ответы:

Да.

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

$k$
$k^{\log(k)/25}$

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

$k$
$k^{\log(k)/25}$

$k$

$\alpha$ $\Delta$ $c$ $G$ $\Delta$ $G$ $c$ $\alpha c$

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

Юкка Суомела
источник

Δ

$\Delta$

c_{1}

$c_1$

c_{2}

$c_2$

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

Юкка Суомела

k

$k$

Δ

$\Delta$

c_{1}

$c_1$

c_{2}

$c_2$

k c_{1} < c_{2}

$kc_1<c_2$

@ AndrewD.King: Да, я буду редактировать ответ; надеюсь, это будет иметь больше смысла. :)

Юкка Суомела