Przybliżone zabarwienie wykresu z obiecaną górną granicą na maksymalnym niezależnym zestawie

W mojej pracy powstaje następujący problem:

Czy istnieje znany algorytm, który aproksymuje liczbę chromatyczną wykresu bez niezależnego zestawu rzędów 65? (Więc alfa (G) <= 64 jest znane, a | V | / 64 jest trywialną dolną, | V | trywialną górną granicą. Ale czy istnieją lepiej udowodnione przybliżenia w tych szczególnych warunkach?)

Co jeśli zrelaksujemy się do ułamkowej liczby chromatycznej? A do „dobrych” czasów pracy w przeciętnych przypadkach?

— cyrix42
źródło

Myślę, że to doskonałe pytanie dla tej strony; miejmy nadzieję, że ktoś ma dobrą odpowiedź.

— Jukka Suomela,

@TysonWilliams: Myślę, że pytanie jest całkowicie jasne. Zapomnij o komentarzu, przeczytaj ponownie pytanie. :)

— Jukka Suomela,

Zabawne jest to, że te warunki gwarantują, że trywialne przybliżenie to 64-przybliżenie optymalnego. Zastanawiam się, czy tylko obietnica małej liczby niezależności może dać lepszy algorytm.

— Sasho Nikolov

Czy problem jest motywowany praktycznym zastosowaniem? Jeśli tak, należy skupić się na interesujących heurystykach, które mają się dobrze - poprawa trywialnego przybliżenia 64 nie jest aż tak interesująca.

— Chandra Chekuri,

O (n^{64})

$O(n^{64})$

Odpowiedzi:

Oblicz maksymalne dopasowanie w dopełnieniu wykresu wejściowego. Każdy niedopasowany węzeł musi być w innej klasie kolorów w dowolnym kolorze. Tak więc: jeśli uzyskasz co najmniej cn dopasowane krawędzie, wówczas samo dopasowanie daje kolorowanie z górną granicą (1-c) n i przybliżonym współczynnikiem 64 (1-c). Jeśli nie uzyskasz co najmniej krawędzi cn, otrzymasz dolną granicę (1 - 2c) n kolorów i współczynnik przybliżenia 1 / (1-2c). Rozwiązanie równania 64 (1-c) = 1 / (1-2c) prowadzi do stosunku aproksymacji nieco większego niż 32; zobacz komentarz Sasho Nikolova, aby uzyskać dokładną wartość.

— David Eppstein
źródło

c = 3 / 16 (4 - \sqrt{2}) \approx 0.5

$c = 3/16 (4-\sqrt{2}) \approx 0.5$

\approx 32

$\approx 32$

k

$k$

α (G)

$\alpha(G)$

\frac{k}{2}

$\frac{k}{2}$

k

$k$

$H$ $H$

http://en.wikipedia.org/wiki/Colouring_number#Al Algorytmy

— Andrew D. King
źródło

Drobna korekta: nieprawda, że liczba kolorów odpowiada najmniejszej liczbie kolorów w zachłannym kolorze. Jeśli zamówisz wierzchołki zgodnie z ich kolorami w optymalnej kolorystyce (z dodatkową właściwością, że pierwsza klasa kolorów jest maksymalna, a druga jest maksymalna na pozostałym wykresie itp.), Wówczas zachłanny algorytm znajdzie tę samą optymalną kolorystykę.

— David Eppstein,