Zamieszanie na temat pokrycia wierzchołków zliczania redukcji do pokrycia cykli liczenia

To mnie dezorientuje.

Jednym z łatwych przypadków liczenia jest sytuacja, gdy problem decyzyjny występuje w i nie ma rozwiązań.$P$

Wykład pokazuje, że problem zliczania liczby idealnych dopasowań na grafie dwustronnym (równoważnie, zliczanie liczby okładek cykli na ukierunkowanym wykresie) jest -kompletny.$\#P$

Dają one redukcję z liczenia okładek wierzchołków o rozmiarze do liczenia okładek cykli w digrafie za pomocą gadżetów.$k$

Twierdzenie 27,1 Liczba okładek dobrych cykli w jest ( k ! ) 2 razy większa od liczby pokryw wierzchołków G o rozmiarze k .$H$$(k!)^2$$G$$k$

Używając gadżetu, pozostawiają tylko „dobre” cykle.

Rozumiem wykład, że nie ma pokrycia wierzchołków o rozmiarze k, jeśli transformowany digraf G ′ nie ma pokrycia cyklu. Sprawdzanie, czy G ′ ma pokrycie cyklu, można wykonać w czasie wielomianowym, sugerując, że P = N P, ponieważ możemy przekształcić problem decyzyjny w znalezienie rozwiązania.$G$$k$$G'$$G'$$P=NP$

Co ja mylę?

$\#P$

$P$

$P \ne NP$$NP$$(0,1)$$0 \mapsto 0$

Edytuj powiązane pytanie MO

Dodany

Markus Bläser zwraca uwagę, że zły cykl wciąż istnieje, ale suma ich wag zanika.

Wydaje mi się, że waga złego cyklu w widżecie wynosi zero.

Od strony 148 (11 pdf):

Macierz pełnego przylegania B z podmacierzami A odpowiadającymi tym widżetom czterowęzłowym liczy 1 dla każdego pokrycia dobrego cyklu w H i 0 dla każdego pokrycia złego cyklu

Inne pytanie:

$k$

W CC każdy wierzchołek musi znajdować się dokładnie w jednym cyklu.

Wygląda na to, że nieporozumienie jest następujące:

W końcowej redukcji do (0,1) -stałej używają arytmetyki modułowej, co łamie mój argument.

$A$$B$

$n$$perm(A)=0$$perm(B)=mn$

$n$$B$

Nie znalazłem wady w pytaniu dotyczącym maksymalnej ważonej ochrony cyklu, na którą nie wydaje się mieć wpływu powyższe.