Czy istnieje bezpośrednia / naturalna redukcja, aby liczyć niedwustronne idealne dopasowania za pomocą stałego?

Zliczanie liczby idealnych dopasowań na wykresie dwustronnym można natychmiast zredukować do obliczenia wartości stałej. Ponieważ znalezienie idealnego dopasowania na grafie dwustronnym występuje w NP, istnieje pewna redukcja z grafów dwustronnych do stałych, ale może to wiązać się z nieprzyjemnym wielomianowym powiększeniem poprzez zastosowanie redukcji Cooka do SAT, a następnie twierdzenia Valianta, aby zredukować do stały.

Skuteczna i naturalna redukcja z grafu dwustronnego do macierzy gdzie $f$ $G$ $A = f(G)$ przydałby się w rzeczywistej implementacji do policzenia idealnych dopasowań przy użyciu istniejących, mocno zoptymalizowanych biblioteki obliczające wartość stałą. $\operatorname{perm}(A) = \Phi(G)$

Zaktualizowano: Dodałem nagrodę za odpowiedź, w tym wydajnie obliczalną funkcję przeniesienia dowolnego wykresu na dwustronny wykres z taką samą liczbą idealnych dopasowań i nie więcej niż wierzchołkami. $G$ $H$ $O(n^2)$

graph-theory counting-complexity reductions permanent Derrick Stolee
źródło

Obecny tytuł brzmi jak zadanie domowe, ale pytanie jest o wiele bardziej interesujące. Prawie nawet nie otworzyłem pytania b / c Myślałem, że to zadanie domowe i wkrótce zostanie zamknięte, dopóki nie zobaczyłem, że ma już 9 głosów pozytywnych i zainteresowałem się ... Może zmień tytuł na coś bardziej podobnego do: Czy istnieje bezpośrednia / naturalna redukcja, aby liczyć niedwustronne idealne dopasowania za pomocą stałego? ”

Joshua Grochow

Dobry pomysł. Nawet o tym nie myślałem. Dzięki.

Derrick Stolee

Nitpicking: „Od znalezienia idealnego dopasowania na grafie dwustronnym jest NP” → → „Od policzenia idealnych dopasowań na grafie dwustronnym jest na #P”

Tsuyoshi Ito

Twoje podrywanie jest poprawne i rozważałem napisanie tego, ale sposób, w jaki to napisałem, wskazuje, że redukcja dotyczy obniżek Cooka TO WALUTA. Szukam bezpośredniej, skutecznej redukcji.

Derrick Stolee

Jest ograniczenie, które pozwala uniknąć Cooka: najpierw napisz formułę VNP dla idealnych dopasowań (mogę pomyśleć o takiej, która jest bardzo podobna do tej dla stałej i która ma rozmiar

). Następnie przez uniwersalność permanentu można to zapisać jako permanent matrycy o rozmiarze

. Wykorzystuje to fakt, że formułę rozmiaru

można zapisać jako stałą macierzy rozmiaru

. Bardziej bezpośredni niż przejście przez Cooka, ale wciąż nie tak bezpośredni / naturalny, jak sposób, w jaki perm liczy doskonałe dopasowania na dwuczęściowym wykresie.

\leq 4 n^{4}

$\leq 4n^4$

4 n^{4} + 1

$4n^4 +1$

S

$S$

S + 1

$S+1$

Joshua Grochow

Odpowiedzi:

Powiedziałbym, że „prosta” redukcja do dwustronnego dopasowywania jest wysoce nieprawdopodobna. Po pierwsze, dałby algorytm do znalezienia idealnego dopasowania na ogólnym wykresie przy użyciu metody węgierskiej. Dlatego redukcja powinna zawierać całą złożoność algorytmu kwitnienia Edmonda. Po drugie, da kompaktowy LP dla idealnego dopasowania politopu, a zatem redukcja nie powinna być symetryczna (co wyklucza wynik Yannakakisa) i z natury bardzo skomplikowana.

Mohit Singh
źródło

Są to wszystkie dobre powody, dla których jest mało prawdopodobne. Powinienem był poprosić o odrzucenie pytania. Prawdopodobnie dam nagrodę za tę odpowiedź, chyba że ktoś udowodni, że się mylisz.

Derrick Stolee

Mimo że nie była to odpowiedź, której chciałem, uznałem tę odpowiedź za bardzo satysfakcjonującą.

Derrick Stolee

@MohitSingh Czy mógłbyś rozwinąć „nieistnienie węgierskiej metody dla grafów dwudzielnych”, „co zawiera całą złożoność algorytmu kwitnienia” i dlaczego miałoby to dać „kompaktowy LP dla idealnego dopasowania i dlatego nie powinien być symetryczny” ?

T ....

To oczywiście komentarz, a nie odpowiedź, ale nie mam tu jeszcze żadnych punktów reputacji, przepraszam za to.

W przypadku dwustronnych sześciennych wykresów bez mostków istnieje wykładniczo wiele doskonałych dopasowań, jak przypuszczali Lovàsz i Plummer w latach 70. Artykuł jest w przygotowaniu. Może to być bardzo istotne dla twojego pytania, a może wcale nie.

Andrew D. King
źródło