Confusão sobre a redução da contagem de capas de vértices para capas de ciclos de contagem

Isso me confunde.

Um caso fácil de contagem é quando o problema de decisão está em e não há soluções.$P$

Uma palestra mostra que o problema de contar o número de combinações perfeitas em um gráfico bipartido (equivalente a contar o número de capas de ciclo em um gráfico direcionado) é completo.$\#P$

Eles reduzem a contagem de capas de vértices do tamanho para capas de ciclos de contagem em um dígrafo usando gadgets.$k$

Teorema 27.1 O número de coberturas boas de ciclo em é ( k ! ) 2 vezes o número de coberturas de vértices de G do tamanho k .$H$$(k!)^2$$G$$k$

Usando o gadget, eles deixam apenas os ciclos "bons".

Meu entendimento da palestra é que não tem cobertura de vértice de tamanho k se o dígrafo transformado G ' não tiver cobertura de ciclo. Verificar se G ' tem cobertura de ciclo pode ser feito em tempo polinomial, implicando P = N P, pois podemos transformar o problema de decisão em encontrar solução.$G$$k$$G'$$G'$$P=NP$

O que estou entendendo mal?

$\#P$

$P$

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

Editar pergunta MO relacionada

Adicionado

Markus Bläser assinala que o ciclo ruim ainda está "lá", mas a soma de seus pesos desaparece.

Parece-me que o peso do ciclo ruim em um widget é zero.

Na página 148 (11 do pdf):

A matriz de adjacência completa B com submatrizes A correspondentes a esses widgets de quatro nós conta 1 para cada cobertura de ciclo bom em H e 0 para cada cobertura de ciclo ruim

Outra pergunta:

$k$

No CC, todo vértice deve estar em exatamente um ciclo.

Parece que o mal-entendido é este:

Na redução final para (0,1) -permanente, eles estão usando aritmética modular, o que quebra meu argumento.

$A$$B$

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

$n$$B$

Não encontramos a falha na pergunta sobre a cobertura máxima do ciclo ponderado, que não parece ser afetada pelo que foi dito acima.