Problem ODD NAWET DELTA

Niech będzie wykresem. Niechbyć liczbą całkowitą. Niech będzie liczbą indukowanych przez krawędź posiadających wierzchołków i nieparzystą liczbę krawędzi. Niech będzie liczbą podgraphów indukowanych przez krawędź, mających wierzchołków i parzystą liczbę krawędzi. Niech . Problem ODD NAWET DELTA polega na obliczeniu , biorąc pod uwagę i . $G = ( V, E )$ $k \leq |V|$ $O_k$ $G$ $k$ $E_k$ $G$ $k$ $\Delta_k = O_k - E_k$ $\Delta_k$ $G$ $k$

pytania

Czy można obliczyć $\Delta_k$ w czasie wielomianowym? Jaki jest najbardziej znany algorytm do jego obliczania?

Co jeśli $G$ jest 3-regularny?

Co jeśli $G$ jest 3-regularnym dwustronnym?

Co jeśli $G$ jest 3-regularnym planem dwustronnym?

ds.algorithms graph-theory graph-algorithms counting-complexity Giorgio Camerani
źródło

Jaka jest twoja motywacja?

Tyson Williams,

@TysonWilliams: Moją motywacją jest to, że jeśli pierwsza część pierwszego pytania ma twierdzącą odpowiedź (nawet tylko w przypadku dwustronnego 3-regularnego przypadku planarnego), wówczas byłyby interesujące konsekwencje zasługujące na dalsze badanie. Jeśli algorytm jest sub wykładniczy, nadal miałby pewne konsekwencje (mniej interesujące, ale mimo to zasługujące na więcej badań).

Giorgio Camerani,

Czy mógłbyś to sprecyzować? Co rozumiesz przez „kilka interesujących konsekwencji”? W jaki sposób napotkałeś ten problem?

Tyson Williams

@TysonWilliams: Czy możemy kontynuować tę rozmowę prywatnie, przez e-mail?

Giorgio Camerani,

AKTUALIZACJA:

Powinienem zwrócić uwagę, że poniższa odpowiedź dotyczy specjalnego przypadku. Ponieważ ten przypadek jest trudny, problem dotyczący ogólnego jest również trudny. $k = |V|$ $k$

Struktura Holanta jest w zasadzie wykładniczą sumą obejmującą wszystkie podgrupy (tzn. Wszystkie wierzchołki są obecne w podgrodzie, więc suma jest nad podzbiorami krawędzi). W przeciwieństwie do tego, obecna wersja pytania dotyczy subgraf wywołanych przez krawędzie.

Wcześniejsza wersja tego pytania dotyczyła zliczania niektórych podgrafów bez izolowanych wierzchołków. Poniższa odpowiedź poprawnie spełnia ten wymóg. Przy rozpatrywaniu zarówno podpakrafów obejmujących (tj. Szkielet Holanta), jak i żadnych izolowanych wierzchołków, jest to to samo, co rozważanie podpunktów indukowanych krawędziami za pomocąwierzchołki. PO zasadniczo wskazał na to w tym pytaniu . $|V|$

3-regularne wykresy planarne

Na razie zignoruję twoje wymaganie, aby wykres był dwustronny. $G$

Załóżmy, że jest 3-regularnym wykresem planarnym. Twój problem można wyrazić jako dwustronny planarny problem Holanta $G$

Pl-Holant ([1, 0, - 1] | [0, 1, 1, 1]) .

$\text{Pl-Holant}([1,0,-1]|[0,1,1,1]).$

Pozwól, że wyjaśnię jak. Aby uzyskać więcej szczegółów niż podam poniżej, zobacz ten artykuł .

Holant to suma (boolowskie) przypisań do krawędzi. Na wierzchołkach znajdują się ograniczenia, których dane wejściowe są przypisane do ich krawędzi zdarzeń. Dla każdego przypisania do krawędzi bierzemy iloczyn wszystkich ograniczeń wierzchołków.

Wymaganie, aby nie było izolowanych wierzchołków, jest ograniczeniem, które nie jest spełnione na danym wierzchołku, jeśli żadna z jego krawędzi nie jest wybrana i jest spełnione, jeśli wybrano co najmniej jedną krawędź. Owo symetryczne ograniczenie jest oznaczone przez [0,1,1,1], co daje 0 (tzn. Niezadowolenie), gdy liczba wejść 1 wynosi 0 (tj. Brak krawędzi incydentu w podrozdziale) i wyjścia 1 (tj. Spełnienie), gdy liczba 1 wejściowych to 1, 2 lub 3 (tj. 1, 2 lub 3 krawędzie padające w podgrafie).

Drugim wymaganiem jest obliczenie liczby podgrafów o parzystej liczbie krawędzi minus podgrupy z nieparzystą liczbą krawędzi. W naszym wykresie każdą krawędź zastępujemy ścieżką o długości 2 (która jest również nazywana 2-odcinkiem ). Daje to (2,3) nieregularny dwustronny wykres. Do wszystkich oryginalnych wierzchołków przypisujemy ograniczenie [0,1,1,1] z góry. Do wszystkich nowych wierzchołków przypisujemy ograniczenie [1,0, -1]. Ponieważ środkowy wpis tego ograniczenia wynosi 0, wymusza to, aby krawędziom padającym tych wierzchołków stopnia 2 albo albo przypisano 0 (tj. Nie w podgrodzie), albo oba zostały przypisane 1 (tj. W podgrodzie). Teraz konkretne przypisanie do krawędzi, jeśli liczba $G$ $G$ $n$ „oryginalnych” krawędzi jest równa, wówczas udział wszystkich wierzchołków stopnia 2 wynosi . W przeciwnym razie jest nieparzyste, a udział wynosi . To jest dokładnie to, czego chcesz. $(-1)^n = 1$ $n$ $(-1)^n = -1$

Ten dwustronny problem Holanta jest # P-trudny według Twierdzenia 6.1 w tym artykule . Jednak twierdzenie to nie jest najłatwiejsze do zastosowania. Zamiast tego rozważ następujące kwestie.

Wykonujemy holograficzną transformację za pomocą co nie zmienia wartości Holanta. Zatem powyższy problem jest dokładnie taki sam jak $T = \begin{bmatrix} -1 & 1 \\ 0 & 1 \end{bmatrix},$

\begin{aligned} Pl-Holant ([1, 0, - 1] | [0, 1, 1, 1]) & = Pl-Holant ([1, 0, - 1] T^{\otimes 2} | (T^{- 1})^{\otimes 3} [0, 1, 1, 1]) \\ = Pl-Holant ([1, - 1, 0] | [1, 0, 0, 1]) . \end{aligned}

$\begin{align*} \text{Pl-Holant}([1,0,-1]|[0,1,1,1]) &= \text{Pl-Holant}([1,0,-1] T^{\otimes 2}|(T^{-1})^{\otimes 3}[0,1,1,1])\\ &= \text{Pl-Holant}([1,-1,0]|[1,0,0,1]). \end{align*}$

Łatwo więc zauważyć, że ten problem jest trudny do #P według twierdzenia 1.1 w tym artykule .

Ograniczanie do wykresów dwustronnych

Podobnie jak w poprzednim pytaniu , ten sam problem ograniczony do grafów dwustronnych jest znacznie trudniejszy do rozwiązania i uważam, że nadal jest to problem otwarty. Mamy przypuszczenie co do przypadków możliwych do przełknięcia (i sprawdzę, czy twój problem jest jednym z nich), ale myślę, że twój problem jest nadal trudny do rozwiązania nawet w przypadku grafów dwustronnych.

Tyson Williams
źródło

Dziękujemy za poświęcenie czasu na to pytanie i udzielenie tak szczegółowej odpowiedzi. Nie znając frameworku Holanta, potrzebuję trochę czasu, aby go przeanalizować i w pełni przetworzyć twoje rozumowanie (oczywiście nie mam wątpliwości co do jego poprawności, po prostu chcę zrozumieć każdy krok, nie tylko wniosek) . Jeśli chodzi o ograniczenie dwuczęściowości, tak, byłoby naprawdę miło, gdybyś mógł sprawdzić, czy domniemanie spraw możliwych do przejęcia obejmuje mój problem.

Giorgio Camerani,

Problem ODD NAWET DELTA

Odpowiedzi:

AKTUALIZACJA:

3-regularne wykresy planarne

Ograniczanie do wykresów dwustronnych