Deterministyczny algorytm równoległy do ​​idealnego dopasowania na ogólnych wykresach?

W klasie złożoności istnieją pewne domniemania, że ​​NIE występują w klasie , tj. Problemy z deterministycznymi algorytmami równoległymi. Problem maksymalnego przepływu jest jednym z przykładów. I są problemy, WIĘCEJ, że są w , ale dowód jeszcze nie został znaleziony.N C N $\mathsf{P}$$\mathsf{NC}$$\mathsf{NC}$

Znakomite dopasowanie problemem jest to jeden z najbardziej podstawowych problemów poruszonych w teorii grafów: podany wykres , musimy znaleźć idealne dopasowanie do . Jak mogłem znaleźć w Internecie, pomimo pięknego algorytmu Blossom wielomianowego czasu opracowanego przez Edmondsa oraz algorytmu RANDOMIZED równoległego autorstwa Karpa, Upfala i Wigdersona w 1986 r., Wiadomo, że tylko kilka podklas grafów ma algorytmy .G N $G$$G$$\mathsf{NC}$

W styczniu 2005 r. Na blogu znajduje się post zatytułowany Złożoność obliczeniowa, który twierdzi, że pozostaje otwarte, czy Perfect Matching znajduje się w . Moje pytanie brzmi:$\mathsf{NC}$

Czy od tego czasu jest jakiś postęp, poza randomizowanym algorytmem ?$\mathsf{NC}$

Aby wyjaśnić moje zainteresowanie, każdy algorytm, który zajmuje się grafami OGÓLNYMI, jest miły. Chociaż algorytmy dla podklas grafów też są w porządku, to może nie być na moją uwagę. Dziękuję wam wszystkim!

EDYCJA o 12/27:

Dziękuję za wszelką pomoc, staram się podsumować wszystkie wyniki w jednym rysunku:

Najniższe znane klasy zawierają następujące problemy:

• Pasujące do ogólnych wykresów: [ KUW86 ], [ CRS93 ]$\mathsf{RNC}$$\mathsf{RNC}^2$
• Dopasowywanie w dwustronnych grafach płaskich / stałych: / [ DKT10 ] / [ DKTV10 ]S P $\mathsf{UL}$$\mathsf{SPL}$
• Dopasowywanie, gdy liczba całkowita jest wielomianowa: [ H09 ]$\mathsf{SPL}$
• Maksymalne dopasowanie do Lexa: [ MS89 ]$\mathsf{CC}$

Ponadto, przy założeniu prawdopodobnej złożoności: wymaga obwodów wykładniczych, dopasowanie w ogólnych wykresach jest w [ ARZ98 ].S P $\mathsf{SPACE[n]}$$\mathsf{SPL}$

$NC$Algorytmy dla idealnych dopasowań na ogólnych wykresach są nadal otwarte, ale odnotowano pewien postęp. Oto kilka, które znam:

W przypadku ogólnych wykresów Agrawal-Hoang-Thierauf wykazał, że biorąc pod uwagę obietnicę, że liczba idealnych dopasowań jest niewielka, istnieje algorytm do zliczenia ich wszystkich.$NC^2$

Dla klasy płaskich wykresów pfaffian odgrywa dużą rolę. Kastelyn pokazał, w jaki sposób każdy płaski plan może być zorientowany w taki sposób, że pfaffian dokładnie równa się liczbie idealnych dopasowań. (Zostało to wykorzystane przez Valiant w celu podania „ algorytmów holograficznych ” dla różnych problemów) Mahajan-Subramanya-Vinay pokazał, jak pfaffian można obliczyć w za pomocą modyfikacji sekwencji clow. (Kastelyn w rzeczywistości podaje algorytm znajdujący osadzanie w ale nie jestem pewien, czy osadzanie pfaffian można również obliczyć w ; jeśli tak, oznaczałoby to, że zliczanie idealnych dopasowań w grafach płaskich jest w .)P N C N $NC$$P$$NC$$NC$

Niedawny wynik Vinodchandrana-Tewariego pokazuje, że lemat izolacji można „derandomizować” dla grafów płaskich (używając twierdzenia Greena!), Aby umieścić osiągalność planarną w . Ale algorytmy dla dopasowań planarnych są nadal otwarte (dzięki Raghunathowi za skorygowanie mojego twierdzenia, że ​​jest w ). algorytm dwudzielnych płaskich skojarzeń podał Datta-Kulkarni-RoyN C U L N $UL$$NC$$UL$$NC$

Mam nadzieję że to pomoże.

Kilka lat później :) i Perfect Matching jest teraz znany z Quasi-NC (to znaczy, że potrzebujesz quasi-wielomianowo wielu procesorów). Zobacz artykuł Fennera, Gurjara i Thieraufa (dla dwustronnych wykresów) https://arxiv.org/pdf/1601.06319.pdf i naszą pracę z Olą Svensson (dla ogólnych wykresów): https://arxiv.org/pdf/1704.01929

Derandomizacja lematu izolacyjnego przez Tewari-Vinodchandran niestety nie daje górnej granicy UL w dopasowaniu planarnym. W rzeczywistości nawet nie sądzę, że algorytm NC nie jest znany z dopasowywania płaskiego. Ale w niedawnej pracy z Dattą, Kulkarni i Nimbhorkarem pokazujemy górną granicę UL dla dwustronnego dopasowania planarnego (zapisywanie tego wyniku jest nadal w toku). Jest to interesujące, ponieważ wcześniej nawet granica NL nie była znana z tego problemu.

Kiedy wiadomo, że problem optymalizacji jest trudny, zwykle sprawdza się ich maksymalne wersje. Na przykład, podczas gdy zestaw niezależny to NP-Complete, leksymalny pierwszy maksymalny zestaw niezależny, czyli P-Complete.

$\sqrt n$

Wszystkie te punkty mówią, że może nie istnieć łatwa do zrównoleglenia wersja NC. Ale kto wie? Ktoś może odstąpić od wersji RNC w przyszłym tygodniu!

Edycja: Dzięki Ramprasad. Ale oto kolejny link do gazety.

$(1-\epsilon)-$$NC$$n^{\Theta(1/\epsilon)}$$O(\log^3 n)$

T. Fischer, AV Goldberg, DJ Haglin i S. Plotkin. Przybliżanie dopasowań równolegle. Informacje Proc. Lett., 46 (3): 115, 1993