Härte der Approximation der gebrochenen chromatischen Zahl in Graphen mit begrenztem Grad

Ist es ungefähr schwierig, die gebrochene chromatische Zahl in Graphen mit begrenztem Grad zu approximieren?

Ja.

Wenn ich es richtig verstanden habe, zeigt der Beweis von Satz 1.6 in Khot (2001) , dass es NP-schwer ist, zwischen den folgenden beiden Fällen zu unterscheiden, selbst wenn wir uns auf Graphen mit begrenztem Grad von ausreichend hohem Grad konzentrieren:

1. Es gibt eine Farbe.$k$
2. Das Verhältnis der Anzahl der Eckpunkte zur maximalen Größe einer unabhängigen Menge beträgt mindestens .$k^{\log(k)/25}$

Aus der Perspektive der gebrochenen chromatischen Zahl sind diese beiden Fälle:

1. Die gebrochene chromatische Zahl beträgt höchstens .$k$
2. Die gebrochene chromatische Zahl beträgt mindestens .$k^{\log(k)/25}$

Jetzt müssen wir uns daran erinnern, dass wir ausreichend hohe Grade benötigen (als Funktion von ). Aber soweit ich sehen kann, hat der Beweis z. B. die folgende praktische Folgerung, die für Ihre Zwecke möglicherweise bereits ausreicht:$k$

• Wenn eine Konstante , gibt es Konstanten Δ und c, so dass das folgende Problem in NP-hart ist: Wenn ein Graph G mit dem maximalen Grad Δ gegeben ist , entscheide, ob die gebrochene chromatische Zahl von G höchstens c oder mindestens α c ist .$\alpha$$\Delta$$c$$G$$\Delta$$G$$c$$\alpha c$

Dies impliziert natürlich bereits, dass es kein PTAS gibt, es sei denn, P = NP.