Załóżmy, że rozwiązujemy problem zliczania prawidłowych zabarwień, licząc ważone zabarwienia w następujący sposób: każde prawidłowe zabarwienie otrzymuje wagę 1, a każde niewłaściwe zabarwienie otrzymuje wagę gdzie jest w pewnym stopniu stałe, a to liczba krawędzi z punktami końcowymi ma ten sam kolor. Gdy zmienia się na 0, sprowadza się to do zliczania odpowiednich kolorów, co jest trudne dla wielu wykresów. Gdy c wynosi 1, każde zabarwienie ma taką samą wagę, a problem jest trywialny. Gdy macierz przylegania wykresu pomnożona przez ma promień spektralny poniżej c v c - log ( c ) / 2 1 - ϵ, suma ta może być przybliżona przez propagowanie przekonań z gwarancją zbieżności, więc jest to łatwe w praktyce. Jest to również łatwe w teorii, ponieważ dane drzewo obliczeniowe wykazuje zanik korelacji, a zatem pozwala na algorytm wielomianowy dla gwarantowanego przybliżenia - Tetali, (2007)
Moje pytanie brzmi - jakie inne właściwości wykresu utrudniają ten problem lokalnym algorytmom? Trudne w tym sensie, że można rozwiązać tylko niewielki zakres .
Edytuj 09/23 : Do tej pory natknąłem się na dwa deterministyczne algorytmy wielomianowej aproksymacji dla tej klasy problemu (pochodne papieru STOC2006 Weitza i podejścia Gamarnika do „ekspansji wnęki” do przybliżonego zliczania), i oba podejścia zależą od czynnika rozgałęziającego samo- unikanie spacerów po wykresie. Promień widmowy pojawia się, ponieważ jest to górna granica tego czynnika rozgałęziającego. Pytanie brzmi zatem - czy jest to dobry szacunek? Czy moglibyśmy mieć sekwencję wykresów, w których czynnik rozgałęzienia spacerów unikających się jest ograniczony, a współczynnik rozgałęzień regularnych spacerów rośnie bez ograniczeń?
Edycja 10/06 : Ten artykuł Allana Sly'ego (FOCS 2010) wydaje się istotny ... wynik sugeruje, że czynnik rozgałęziający się w nieskończonym drzewie samowystarczalnych spacerów precyzyjnie oddaje moment, w którym liczenie staje się trudne.
Edycja 10/31 : Alan Sokal przypuszcza (s. 42 z „Wielowymiarowej wielomianu Tutte” ), że istnieje górna granica na promieniu obszaru zerowego wielomianu chromatycznego, który jest liniowy pod względem maksymalnego przepływu (maksymalny przepływ ponad wszystkie pary s, t). Wydaje się to istotne, ponieważ korelacje dalekiego zasięgu pojawiają się, gdy liczba prawidłowych kolorów zbliża się do 0.
źródło
Odpowiedzi:
Jest to trudne w przypadku wykresów płaskich, przynajmniej dla sześciu kolorów lub więcej. Zobacz „Niedopuszczalność wielomianu Tutte wykresu płaskiego” autorstwa Goldberga i Jerruma
źródło
Więcej komentarzy:
Lokalny algorytm zliczania obliczy liczbę ze zbioru statystyk dla każdego węzła, gdzie każda statystyka jest funkcją pewnego sąsiedztwa grafowego węzła. W przypadku zabarwienia statystyki te są powiązane z „marginalnym prawdopodobieństwem napotkania koloru c”. Oto przykład tej redukcji dla prostego wykresu.
Z ostatniego artykułu Alana Sly'ego wynika, że zliczanie niezależnych zestawów przy użyciu lokalnego algorytmu jest tak trudne, jak liczenie niezależnych zestawów przy użyciu dowolnego algorytmu. Podejrzewam, że dotyczy to ogólnego liczenia na wykresach.
W przypadku algorytmów lokalnych twardość zależy od tego, jak zachowuje się korelacja między węzłami w odniesieniu do odległości między węzłami. W przypadku wystarczająco dużych odległości ta korelacja zasadniczo ma tylko dwa zachowania - albo korelacja zanika wykładniczo w odległości wykresu, albo w ogóle nie zanika.
Jeśli występuje rozkład wykładniczy, lokalne statystyki zależą od sąsiedztwa, którego rozmiar jest wielomianowy pod względem wielkości wykresu, więc problem zliczania jest łatwy.
W statystycznych modelach fizyki zauważono (tj. De Gennesa, Emery'ego), że istnieje związek między samodzielnymi spacerami, zanikiem korelacji i przemianami fazowymi. Punkt, w którym funkcja generowania dla unikających się spacerów po sieci staje się nieskończona, odpowiada temperaturze, w której w modelu pojawiają się korelacje dalekiego zasięgu.
Z konstrukcji drzewka chodzącego weitz można zobaczyć, dlaczego spacery omijające pojawiają się w rozpadzie korelacji - margines można przedstawić dokładnie jako rdzeń drzewa spacerów samouczących się, więc jeśli czynnikiem rozgałęziającym to drzewo jest wystarczająco małe, liście drzewa stają się w końcu nieistotne.
Jeśli „twardość lokalna” implikuje twardość, wystarczy określić ilościowo właściwości, które określają tempo wzrostu marszów unikających siebie. Dokładną stopę wzrostu można wyodrębnić z funkcji generującej dla unikania spacerów, ale obliczenie jest trudne. Promień spektralny jest łatwy do obliczenia i daje dolną granicę.
źródło
Kilka komentarzy: nie odpowiedź.
Jeśli jest wystarczająco małe w stosunku do liczby wierzchołków na wykresie, wówczas niewłaściwe zabarwienie zsumuje się do mniej niż 1. Stąd trywialne zmniejszenie z przypadku wagi 0 do tego przypadku: po prostu wybierz aby był mały wystarczająco. Oznacza to, że problem jest trudny do # P dla dowolnej kolekcji instancji z , dla każdego . (Tutaj pozwalam, aby był różny w różnych instancjach, więc klasy są związkami klas ze stałym .)c c ∈ [ 0 , ϵ ) ϵ > 0 c cc c c∈[0,ϵ) ϵ>0 c c
Załóżmy teraz, że jest naprawione, tak jak w konfiguracji problemu. W przypadku wystarczająco dużych wykresów zawsze można przekroczyć ważoną sumę 1 w przypadku niewłaściwych kolorów, więc ta bezpośrednia redukcja nie działa.c
Pytasz o właściwości strukturalne klasy grafów, które pozwoliłyby na rozwiązanie problemu. O ile wiem, prawie zawsze będzie to trudne. Ale jest to bardzo szkicowe i wymaga więcej pracy.
źródło