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 ϵ )?
Ł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 )
Dziękuję za uwagę!
cc.complexity-theory
approximation-hardness
graph-colouring
hypergraphs
bounded-degree
afshi7n
źródło
źródło
Odpowiedzi:
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 √K 2Ω((logK)2) 22(logK)2 K d kolorowy wykres zlogiemdkolorów.2loglogd√ logd
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ś na2clogd√ d dc 0<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.
źródło
źródło
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.
źródło
Ten wynik może być pomocny:
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
źródło