Wydajny algorytm do niemal optymalnego kolorowania krawędzi hipergraphów

Problemy z kolorowaniem wykresów są już wystarczająco trudne dla większości ludzi . Mimo to będę musiał być trudny i zapytać o barwienie metodą hypergraph.

Pytanie.

Jakie są skuteczne algorytmy do znalezienia w przybliżeniu optymalnego zabarwienia krawędzi dla hipergraphów jednolitych k?

Detale ---

• Hypergraph k-uniform to taki, w którym każda krawędź zawiera dokładnie k wierzchołków; zwykłym przypadkiem prostego wykresu jest k = 2. Mówiąc dokładniej, interesują mnie oznaczone hipergrrafy k-uniform, w których dwie krawędzie mogą mieć ten sam zestaw wierzchołków; ale zadowolę się czymś na k-regularnych hipergraphach z krawędziami przecinającymi się nie więcej niż k-1 wierzchołkami.

• Kolorowanie krawędzi hypergraphs to takie, w którym krawędzie tego samego koloru nie przecinają się, jak w przypadku wykresów. Indeks chromatyczny χ '(H) jest, jak zwykle, minimalną wymaganą liczbą kolorów.

• Chciałbym wyniki na deterministycznych lub losowych algorytmach wielomianu czasu.

• Szukam najlepiej znanego współczynnika aproksymacji / luki dodatków między tym, co można skutecznie znaleźć, a rzeczywistym indeksem chromatycznym χ '(H) --- lub, w związku z tym, najlepiej osiągalnym wynikiem pod względem parametrów takich jak maksymalny stopień wierzchołka ((H), rozmiar hipergraphu itp.

Edit: prośba o uwagach Suresh za około felg bliźniaczych hipergraf Poniżej Należy zauważyć, że problem ten jest równoznaczny z problemem znalezienia silnego wierzchołek kolorowania z k-regularny hipergraf to znaczy, gdzie każdy wierzchołek należy do k wyraźne krawędzie, [ale krawędzie może teraz zawierać różną liczbę wierzchołków] i chcemy kolorowania wierzchołków tak, aby dowolne dwa sąsiednie wierzchołki miały różne kolory. To przeformułowanie również nie wydaje się mieć oczywistego rozwiązania.

Uwagi

W przypadku grafów Twierdzenie Vizinga nie tylko gwarantuje, że liczba krawędziowo-chromatyczna dla wykresu G wynosi albo Δ (G) lub Δ (G) +1, standardowe dowody tego dają również skuteczny algorytm do znalezienia Δ (G ) + Kolorowanie 1-krawędziowe. Ten wynik byłby dla mnie wystarczająco dobry, gdybym był zainteresowany sprawą k = 2; jednak jestem szczególnie zainteresowany dowolnością k> 2.

Wydaje się, że nie ma żadnych dobrze znanych wyników dotyczących granic kolorowania krawędzi hipergrafu, chyba że dodasz ograniczenia, takie jak każda krawędź przecinająca się co najwyżej t wierzchołków. Ale nie potrzebuję granic samego χ '(H); tylko algorytm, który znajdzie „wystarczająco dobre” zabarwienie krawędzi. [Nie chcę również nakładać żadnych ograniczeń na moje hipergrrafy, z wyjątkiem tego, że są k-jednolite, i być może ogranicza się do maksymalnego stopnia wierzchołka, np.) (H) ≤ f (k) dla niektórych f ∈ ​​ω (1) .]

[ Dodatek. Zadałem teraz pokrewne pytanie na MathOverlow dotyczące granic liczby chromatycznej, konstruktywnych lub innych.]

Poniższa odpowiedź łamie twój warunek, że nie chcesz poważnych ograniczeń nakładanych na twój hipergraph, ale może być interesujący, jeśli tylko jako powiązana praca.

$r$$r$

Niedawno pracowano nad takimi problemami z „kolorowymi kolorami” w przestrzeniach zasięgu geometrycznego, częściowo uzasadnionymi problemami w sieciach czujników. Zadawane standardowe pytanie to:

$k$$S$$c_S(k)$$c_S(k)$$r$$S$$\min(|r|, k)$

Zatem to ilość, której szukasz (gdzie to maksymalna liczność zakresu).$c_S(\Delta)$$\Delta$

Powiązanym pytaniem jest określenie , gdzie to przestrzeń podwójnego zakresu (w efekcie twój oryginalny hipergraph). Jednym z przykładów uzyskanych wyników jest to, że :˜ $c_\tilde{S}(k)$$\tilde{S}$

Ponieważ jest przestrzenią półpłaszczyznową w ,ℜ 2 c S ( k ) ≤ 3 k - $S$$\Re^2$$c_S(k) \le 3k-2$

Dobrym odniesieniem do tego zbioru prac jest praca DCG autorstwa Aloupsis i in. Oraz odnośniki tam zawarte.