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?

ds.algorithms graph-algorithms approximation-algorithms graph-colouring 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,