twardość aproksymacji liczby chromatycznej na wykresach z ograniczonym stopniem

12

Szukam wyników twardości na kolorowanie wierzchołków wykresów z ograniczonym stopniem.

Biorąc pod uwagę wykres , wiemy, że dla dowolnego ϵ > 0 trudno jest oszacować χ ( G ) przy współczynniku | V | 1 - ϵ, chyba że NP = ZPP [ 1 ]. Ale co, jeśli maksymalny stopień G jest ograniczony przez d ? Czy w tym przypadku są jakieś współczynniki twardości postaci d 1 - ϵ (dla niektórych ϵ )?G(V,E)ϵ>0χ(G)|V|1ϵNP=ZPPGdd1ϵϵ

Łatwiejszym pytaniem jest: twardość aproksymacji liczby chromatograficznej krawędzi hipergraphów, gdy ich wielkość krawędzi jest ograniczona przez . Możemy mieć nadzieję na d 1 - ε stosunek twardości w tym przypadku? (powiedzmy, dla dowolnego ϵ > 0 )dd1ϵϵ>0

Dziękuję za uwagę!

afshi7n
źródło
3
możesz wypełnić twardą instancję izolowanymi wierzchołkami
Sasho Nikolov
2
Tak, ale jeśli ograniczysz rozmiar twardej instancji, od której zaczynasz, przestanie być trudna.
David Eppstein,
1
@Sasho W jaki sposób izolowane wierzchołki mogą pomóc, gdy nie zwiększają ani liczby chromatycznej, ani maksymalnego stopnia?
afshi7n
2
@DavidEppstein pewno, to dopełnienie udowadnia coś tylko wtedy, gdy i d są nadal wielomianowo powiązane. OP, właśnie o to właśnie chodzi. zaczynasz od instancji z wierzchołkami d (czyli maksymalnie o stopień d ), dla których trudno jest zbliżyć χ do d 1 - ϵ . dodaj n - d izolowanych wierzchołków. χ pozostaje taki sam, a maksymalny stopień zostaje d . jest to czas polytime, jeśli N = d O ( 1 ) . więc dla dowolnej liczby całkowitej kndddχd1ϵndχdN=dO(1)kIstnieją przypadki z maksymalny stopień , dla których trudno jest w przybliżeniu χ na odległość d 1 - εd=n1/kχd1ϵ
Sasho Nikołow
Aktualizacja: NP jest trudne do przybliżenia przy współczynniku | V | 1 - ϵ bez żadnych dodatkowych założeń. χ(G)|V|1ϵ
Cyriak Antony

Odpowiedzi:

9

Jak zauważył David, artykuł Khota „Poprawione wyniki niedopuszczalności dla MaxClique, liczby chromatycznej i przybliżonego zabarwienia wykresu”, Twierdzenie 1.6, mówi, że jest trudny do NP kolorowanie wykresu kolorami 2 Ω ( ( log K ) 2 ) dla wykresy z stopniu co najwyżej 2 2 ( log K ) 2 , na wystarczająco dużej stałej K . Innymi słowy, w przypadku wykresów stopnia d trudno jest pokolorować 2 K2Ω((logK)2)22(logK)2Kd kolorowy wykres zlogiemdkolorów.2loglogdlogd

Aby uzyskać lepszy stopień naukowy, prawdopodobnie możesz skorzystać z pomysłów z pracy Trevisana „Wyniki nieprzybliżenia dla problemów z optymalizacją w instancjach z ograniczonym stopniem”. Kluczową obserwacją jest to, że wykres utworzony przez redukcję FGLSS stanowi połączenie kompletnych dwustronnych podsgrafów i każdy z nich można zastąpić dwustronnym dyspergatorem, który jest znacznie rzadszy. Podobny pomysł zastosowano w wielu wynikach, takich jak Chan http://eccc.hpi-web.de/report/2012/110/ , Twierdzenie 1.4 / Dodatek D.

Myślę, że to powinno dać ci coś na 2clogdddc0<c<1

Stopień związany we wspomnianym artykule Michaela jest podobny do stopnia Khota, a mianowicie wykładniczy przypadku dźwiękowego. Oczywiście powyższe podejście do sparsifikacji również to poprawia, ale prawdopodobnie nie da lepszej stałej dla twojego celu.

sangxia
źródło
2Ω(loglogd)22Ω(loglogd)
logd/2loglogdlogd/(loglogd)3dcd
1
dc
8

3

Δ3Δ4

vb le
źródło
8

W artykule FOCS'01 Khota znajduje się wynik niedoceniania dla kolorowania grafów stopni ograniczonych, „Poprawione wyniki niedopuszczalności dla MaxClique, liczby chromatycznej i przybliżonego zabarwienia wykresu” - prawdopodobnie jest słabszy niż chcesz, ale przynajmniej jest we właściwym kierunku.

kk2kO(logk)exp((logk)2/25)dO(logd)

David Eppstein
źródło
logd
Dlaczego nie zapytać Khota?
Chandra Chekuri,
1
@chandra Właśnie wysłałem e-mail i zapytałem go, dziękuję za sugestię! Zaktualizuję tutaj, jeśli się odezwę.
afshi7n
klogk/25exp((klogk)/25)2k1/3
k(logk)/25exp((klogk)/25)
4

Ten wynik może być pomocny:

Δk=ΔΔ+1k3

T. Emden-Weinert, S. Hougardy, B. Kreuter, Wyjątkowo kolorowe wykresy i twardość kolorowych wykresów dużego obwodu, Combin. Probab Comput. 7 (4) (1998) 375–386

Mohammad Al-Turkistany
źródło