Rozkłady grafów do łączenia „lokalnych” funkcji etykietowania wierzchołków

\sum_{x} \prod_{ja jot \in mi} fa (x_{ja}, x_{jot})

$\sum_x \prod_{ij \in E} f(x_i,x_j)$

max_{x} \prod_{ja jot \in mi} fa (x_{ja}, x_{jot})

$\max_x \prod_{ij \in E} f(x_i,x_j)$

Gdzie Max lub suma przejmuje wszystkie labelings z , produkt wprowadza się na wszystkie krawędzie dla grafu i jest dowolną funkcją. Ilość ta jest łatwa do znalezienia dla ograniczonych wykresów szerokości drzewa i ogólnie NP-trudna dla wykresów płaskich. Liczba prawidłowych kolorów, maksymalny niezależny zestaw i liczba podgraphów Eulera to szczególne przykłady powyższego problemu. Interesują mnie schematy aproksymacji czasu wielomianowego dla tego rodzaju problemów, szczególnie dla grafów płaskich. Jakie rozkłady wykresów byłyby przydatne? $V$ $E$ $G=\{V,E\}$ $f$

Edytuj 11/1 : Jako przykład zastanawiam się nad rozkładami, które mogą być analogiczne do rozszerzeń klastrowych fizyki statystycznej (tj. Rozszerzenia Mayera). Gdy $f$ reprezentuje słabe interakcje, takie rozszerzenia są zbieżne, co oznacza, że można osiągnąć określoną dokładność z warunkami $k$ rozwinięcia niezależnie od wielkości wykresu. Czy nie oznaczałoby to istnienia PTAS dla tej ilości?

Aktualizacja 02/11/2011

Rozszerzenia wysokotemperaturowe przepisują funkcję podziału $Z$ jako sumę terminów, w których warunki wyższego rzędu zależą od interakcji wyższego rzędu. Kiedy „rozkładać korelacji”, wysokie Warunków Zamówienia rozpaść na tyle szybko, że prawie wszystkie $Z$ masa jest zawarta w skończonej liczbie warunkach niskiego rzędu.

Na przykład dla modelu Isinga rozważ następujące wyrażenie jego funkcji podziału

Z = \sum_{x \in X} \exp jot \sum_{ja jot \in mi} x_{ja} x_{jot} = do \sum_{ZA \in do} (\tanh jot)^{| ZA |}

$Z=\sum_\mathbf{x\in \mathcal{X}} \exp J \sum_{ij \in E} x_i x_j = c \sum_{A\in C} (\tanh J)^{|A|}$

Tutaj jest prostą stałą, jest zbiorem podgraphów Eulera z naszego wykresu,wiele krawędzi w podgrafu . $c$ $C$ $|A|$ $A$

Przepisaliśmy funkcję podziału jako sumę na podgrupy, gdzie każdy warunek sumy jest wykładniczo karany przez rozmiar podgrupy. Teraz pogrupuj terminy z tym samym wykładnikiem i przybliż , biorąc pierwsze wyrażeń. Gdy liczba podgraphów Eulera wielkości nie rośnie zbyt szybko, błąd naszego przybliżenia maleje wykładniczo z . $Z$ $k$ $p$ $k$

Przybliżone zliczanie jest ogólnie trudne, ale łatwe w przypadkach „zaniku korelacji”. Na przykład w przypadku modelu Isinga występuje zanik korelacji, gdy rośnie wolniej niż gdzie jest liczbą podgraphów Eulera wielkości . Uważam, że w takim przypadku obcięcie ekspansji w wysokiej temperaturze daje PTAS dla $f(k)$ $(\tanh J)^k$ $f(k)$ $k$ $Z$

Innym przykładem jest zliczanie niezależnych zbiorów ważonych - jest to możliwe dla każdego wykresu, jeśli waga jest wystarczająco niska, ponieważ można sprawić, że problem będzie wykazywał zanik korelacji. Ilość jest następnie aproksymowana poprzez zliczanie niezależnych zbiorów w ograniczonych obszarach wielkości. Uważam, że wynik „STOC” 06 Drora Weitza sugeruje, że możliwe jest nieważone niezależne liczenie zbiorów dla każdego wykresu z maksymalnym stopniem 4.

Znalazłem dwie rodziny „lokalnych” rozkładów - wykresy klastrów Bethe i wykresy regionu Kikuchi. Dekompozycja zasadniczo mówi, aby pomnożyć liczby w regionach i podzielić przez liczby w nakładających się na siebie regionach. Metoda wykresu regionu Kikuchi poprawia to, biorąc pod uwagę, że nakładające się regiony mogą same pokrywać się, stosując korektę typu „włączenie-wykluczenie”.

Alternatywnym podejściem jest rozłożenie problemu na globalne części, które można traktować, jak w „Wniosku wariacyjnym na temat przestrzeni kombinatorycznych”. Jednak lokalne dekompozycje pozwalają kontrolować jakość aproksymacji, wybierając rozmiar regionu

— Jarosław Bułatow
źródło

To, co chcę powiedzieć, jest za długie na (ale tak naprawdę powinno być) komentarz.

Jeśli poprawnie czytam pytanie, potrzebujesz FPRAS (w pełni wielomianowy losowy schemat aproksymacji) dla każdej z powyższych wielkości, z których każda zawiera różne problemy z uzupełnieniem # P jako przypadki szczególne. W szczególności potrzebny jest ogólny FPRAS w przypadku grafów płaskich, poprzez zastosowanie rozszerzania klastra.

Wątpię, czy jest to możliwe ze względu na fakt, że zupełność NP problemu istnienia (np. Właściwe zabarwienie) implikuje, że odpowiadający problem liczenia (np. Liczba właściwych zabarwień) jest kompletny w #P w odniesieniu do redukcji AP (przybliżenie- konserwowanie). Patrz Dyer, Goldberg, Greenhill and Jerrum, Al algorytmica (2004) 38: 471-500.

Ale może źle odczytałem pytanie.

(Czy rzeczywiście byłbyś w stanie wyjaśnić niewtajemniczonemu znaczenie ekspansji w wysokiej temperaturze?)

— RJK
źródło

Odpowiedziałem na moje pytanie

— Jarosław Bułatow

@Yaroslav: Dziękuję za obszerne wyjaśnienia! BTW, przez „region” masz na myśli „podzbiór wierzchołków”? (Właśnie to widzę, gdy patrzę na Heske, JAIR 26 (2006), 153-190.) Tak więc wydaje się, że szukacie konkretnych FPRAS (to znaczy ze szczególnym wyborem f) dla określonych klas (jak stopień w większość 4) płaskich wykresów przy użyciu tak zwanego „rozkładu grafu” (co jest bardzo przeciążonym terminem, żeby być uczciwym). Czy to jest poprawne?

— RJK

Tak, regiony to podzbiory wierzchołków, a ja interesuję się PTAS dla „możliwych do przełożenia” klas grafów. BTW, oto opracowany przykład dekompozycji klastrowej do zliczania niezależnych zbiorów, które moim zdaniem można przekształcić w PTAS dla instancji z zanikiem korelacji - yaroslavvb.blogspot.com/2011/02/...

— Jarosław