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 trudno jest przy współczynniku chyba że [ 1 ]. Ale co, jeśli maksymalny stopień jest ograniczony przez ? Czy w tym przypadku są jakieś współczynniki twardości postaci (dla niektórych )? $G(V,E)$ $\epsilon>0$ $\chi(G)$ $|V|^{1-\epsilon}$ $\textit{NP}=\textit{ZPP}$ $G$ $d$ $d^{1-\epsilon}$ $\epsilon$

Łatwiejszym pytaniem jest: twardość aproksymacji liczby chromatograficznej krawędzi hipergraphów, gdy ich wielkość krawędzi jest ograniczona przez . Możemy mieć nadzieję na stosunek twardości w tym przypadku? (powiedzmy, dla dowolnego ) $d$ $d^{1-\epsilon}$ $\epsilon >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

są nadal wielomianowo powiązane. OP, właśnie o to właśnie chodzi. zaczynasz od instancji z wierzchołkami

(czyli maksymalnie o stopień

), dla których trudno jest zbliżyć

do

. dodaj

izolowanych wierzchołków.

pozostaje taki sam, a maksymalny stopień zostaje

. jest to czas polytime, jeśli

. więc dla dowolnej liczby całkowitej

n

$n$

d

$d$

d

$d$

d

$d$

χ

$\chi$

d^{1 - ϵ}

$d^{1-\epsilon}$

n - d

$n - d$

χ

$\chi$

d

$d$

N = d^{O (1)}

$N = d^{O(1)}$

k

$k$ Istnieją przypadki z maksymalny stopień

, dla których trudno jest w przybliżeniu

na odległość

d = n^{1 / k}

$d = n^{1/k}$

χ

$\chi$

d^{1 - ϵ}

$d^{1-\epsilon}$

— Sasho Nikołow

Aktualizacja: NP jest trudne do przybliżenia

przy współczynniku

bez żadnych dodatkowych założeń.

χ (G)

$\chi(G)$

| V |^{1 - ϵ}

$|V|^{1-\epsilon}$

— Cyriak Antony

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 dla wykresy z stopniu co najwyżej , na wystarczająco dużej stałej . Innymi słowy, w przypadku wykresów stopnia trudno jest pokolorować $K$ $2^{\Omega((\log K)^2)}$ $2^{2^{(\log K)^2}}$ $K$ $d$ kolorowy wykres zkolorów. $2^{\sqrt{\log\log d}}$ $\log d$

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 $2^{\sqrt{c\log d}}$ $d$ $d^{c}$ $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.

— sangxia
źródło

2^{Ω (\log \log d)}

$2^{\Omega(\log \log d)}$

2^{2^{Ω (\sqrt{\log \log d})}}

$2^{2^{\Omega(\sqrt{\log \log d})}}$

\log d / 2^{\sqrt{\log \log d}}

$\log d / 2^{\sqrt{\log \log d}}$

\log d / (\log \log d)^{3}

$\log d / (\log\log d)^3$

d^{c}

$d^c$

d

$d$

1

d^{c}

$d^c$

8

$3$

$\Delta$ $3$ $\Delta$ $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.

$k$ $k$ $2^{k^{O(\log k)}}$ $\exp((\log k)^2/25)$ $d$ $O(\log d)$

— David Eppstein
źródło

\log d

$\log d$

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

k^{\log k / 25}

$k^{\log k/25}$

\exp ((k \log k) / 25)

$\exp((k\log k)/25)$

2^{k^{1 / 3}}

$2^{k^{1/3}}$

k^{(\log k) / 25}

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

\exp ((k \log k) / 25)

$\exp((k\log k)/25)$

4

Ten wynik może być pomocny:

$\Delta$ $k=$ $\Delta - \sqrt\Delta +1$ $k\ge 3$

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