Confusion au sujet de la réduction du nombre de couvertures de sommets par rapport aux couvertures de cycles de comptage

Cela m'embrouille.

Un cas facile de comptage est lorsque le problème de décision est en et qu'il n'y a pas de solutions.$P$

Une conférence montre que le problème du comptage du nombre de correspondances parfaites dans un graphique bipartite (de manière équivalente, le comptage du nombre de couvertures de cycle dans un graphique dirigé) est -complete.$\#P$

Ils permettent de passer du comptage des couvertures de sommets de taille au comptage des couvertures de cycle dans un digraphe à l'aide de gadgets.$k$

Théorème 27.1 Le nombre de bonnes couvertures de cycle dans est ( k ! ) 2 fois le nombre de couvertures de sommets de G de taille k .$H$$(k!)^2$$G$$k$

À l'aide de gadgets, ils ne laissent que les «bons» cycles.

Ma compréhension de la conférence est que n'a pas de couverture de sommet de taille k si le digraphe transformé G ' n'a pas de couverture de cycle. Vérifier si G ′ a une couverture de cycle peut se faire en temps polynomial, impliquant P = N P puisque nous pouvons transformer le problème de décision en solution.$G$$k$$G'$$G'$$P=NP$

Qu'est-ce que je comprends mal?

Le permanent de la matrice d'adjacence du cycle de comptage des digrammes couvre et est complet.$\#P$

Le problème de la décision « est le zéro de la matrice permanente de (0,1) » est dans P depuis trouver une couverture de cycle est en .$P$

implique qu'il n'y a pas de réduction du comptage N P - problèmes complets au comptage ( 0 , 1 ) - permanent qui mappe 0 ↦ 0 .$P \ne NP$$NP$$(0,1)$$0 \mapsto 0$

Modifier la question MO associée

Ajoutée

Markus Bläser souligne que le mauvais cycle est toujours "là", mais la somme de leurs poids disparaît.

Il me semble que le poids d'un mauvais cycle dans un widget est nul.

À partir de la page 148 (11 du pdf):

La matrice d'adjacence complète B avec sous-matrices A correspondant à ces widgets à quatre nœuds compte 1 pour chaque bonne couverture de cycle en H et 0 pour chaque mauvaise couverture de cycle

Une autre question:

La couverture du cycle de poids maximal ne contiendrait-elle pas uniquement les bons cycles, correspondant à une couverture de sommets dans le graphique d'origine?$k$

En CC, chaque sommet doit être dans exactement un cycle.

On dirait que le malentendu est le suivant:

Dans la réduction finale à (0,1) -permanent, ils utilisent l'arithmétique modulaire, ce qui brise mon argument.

$A$$B$

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

$n$$B$

Je n'ai pas trouvé la faille dans la question sur la couverture de cycle pondérée maximale, qui ne semble pas être affectée par ce qui précède.