Twardość przybliżonej ułamkowej liczby chromatycznej na wykresach ze stopniem granicznym

Czy trudno jest apx-przybliżać ułamkową liczbę chromatyczną na wykresach ze stopniem granicznym?

— Ashwinkumar BV
źródło

Co to jest ułamkowa liczba chromatyczna?

— Mohammad Al-Turkistany,

@ MohammadAl-Turkistany: LP relexation od liczby chromatycznej, patrz, np en.wikipedia.org/wiki/Fractional_coloring

— Jukka Suomela

Tak.

Jeśli dobrze zrozumiałem, dowód Twierdzenia 1.6 w Khot (2001) stwierdza, że trudno jest rozróżnić następujące dwa przypadki, nawet jeśli skupimy się na grafach stopnia ograniczonego o wystarczająco wysokim stopniu:

Jest kolorowanie. $k$
Stosunek liczby wierzchołków do maksymalnego rozmiaru niezależnego zestawu wynosi co najmniej . $k^{\log(k)/25}$

Z perspektywy ułamkowej liczby chromatycznej te dwa przypadki to:

Ułamkowa liczba chromatyczna wynosi co najwyżej . $k$
Ułamkowa liczba chromatyczna wynosi co najmniej . $k^{\log(k)/25}$

Teraz musimy pamiętać, że potrzebujemy wystarczająco wysokich stopni (w funkcji ). Ale o ile widzę, dowód ma np. Następującą dogodną następstwo, która może być już wystarczająca dla twoich celów: $k$

Biorąc pod uwagę dowolną stałą , istnieje stałe i tak, że po problem NP-trudny: podany wykres maksymalnego stopnia zdecydować, czy ułamkowe liczby chromatycznych wynosi co najwyżej lub co najmniej . $\alpha$ $\Delta$ $c$ $G$ $\Delta$ $G$ $c$ $\alpha c$

Oczywiście oznacza to już, że nie ma PTAS, chyba że P = NP.

— Jukka Suomela
źródło

Na pewno ostatnia konsekwencja ma kilka innych modyfikatorów stałych, w przeciwnym razie jest to bardzo dobrze znane z małych wartości , i ...

Δ

$\Delta$

c_{1}

$c_1$

c_{2}

$c_2$

— Andrew D. King

@ AndrewD.King: Racja, możesz dowolnie zmienić dowolną z nich, itd. Ale być może mógłbyś opublikować odpowiedź, która pokazuje, że prostą wersję wniosku można uzyskać za pomocą starszych i łatwiejszych technik - myślę, że już byłby wystarczy odpowiedzieć na pytanie OP?

— Jukka Suomela

@JukkaSuomela Mam na myśli, że jak stwierdzono, nie dowodzi to twardości APX. Np. Dobrze wiadomo (Holyer, SICOMP, 1980), że wyznaczenie indeksu chromatycznego wykresu sześciennego jest trudne dla NP, co oznacza, że trudno jest ustalić, czy liczba chromatyczna dla wykresu liniowego z maksymalnym stopniem 4 to 4. Myślę, że masz na myśli: Biorąc pod uwagę jakąkolwiek stałą , istnieją stałe , i takie, że , ... Czy to prawda?

k

$k$

Δ

$\Delta$

c_{1}

$c_1$

c_{2}

$c_2$

k c_{1} < c_{2}

$kc_1<c_2$

— Andrew D. King,

@ AndrewD.King: Tak, zmienię odpowiedź; miejmy nadzieję, że w ten sposób będzie bardziej sensowne. :)

— Jukka Suomela