# Confusion about reduction counting vertex covers to counting cycle covers

This confuses me.

One easy case of counting is when the decision problem is in $P$ and there are no solutions.

A lecture show that the problem of counting the number of perfect matchings in a bipartite graph (equivalently, counting the number of cycle covers in a directed graph) is $\#P$ -complete.

They give reduction from counting vertex covers of size $k$ to counting cycle covers in a digraph using gadgets.

Theorem 27.1 The number of good cycle covers in $H$ is $(k!)^2$ times the number of vertex covers of $G$ of size $k$.

Using gadget they leave only the "good" cycles.

My understanding of the lecture is that $G$ doesn't have vertex cover of size $k$ iff the transformed digraph $G'$ doesn't have cycle cover. Checking if $G'$ has cycle cover can be done in polynomial time, implying $P=NP$ since we can transform the decision problem to finding solution.

What am I misunderstanding?

The permanent of the adjacency matrix of digraph counts cycle covers and is $\#P$-complete.

The decision problem "Is the permanent of (0,1) matrix zero" is in P since finding cycle cover is in $P$.

$P \ne NP$ implies there is no reduction of counting $NP$-complete problems to counting $(0,1)$-permanent which maps $0 \mapsto 0$.

Markus Bläser points out that bad cycle are still "there", but the sum of their weights vanishes.

Appears to me the weight of bad cycle in a widget is zero.

From page 148 (11 of the pdf):

The full adjacency matrix B with submatrices A corresponding to these four-node widgets counts 1 for each good cycle cover in H and 0 for each bad cycle cover

Another question:

Wouldn't maximum weight cycle cover contain only the good cycles, corresponding to a $k$ vertex cover in the original graph?

In CC every vertex must be in exactly one cycle.

• They didn't leave only good cycles. In their counting argument they eliminated counting bad cycles. The problem is you have to count #good cycle covers. So if you find a cycle cover which is not a good cycle cover then you cannot obtain a k-vertex cover. But if you find a good cycle cover yes, the graph has k-VC. This does not violate anything. – Saeed Jun 28 '14 at 11:26
• @Saeed isn't eliminating bad cycle the same as counting only good? I don't see how it is possible G' to have any cycle cover if G doesn't have VC of size $k$. – joro Jun 28 '14 at 11:31
• @Saeed Aren't they counting all cycle covers in the transformed G'? – joro Jun 28 '14 at 11:42
• The reduction assigns weights to the edges. Bad cycle covers can have positive or negative weight, there overall contribution is zero. But these cycles are still "there" and might be found by a cycle cover detection algorithm and in this case you do not know whether there is a good cycle cover or not. – Markus Bläser Mar 24 '15 at 8:21
• @MarkusBläser Thank you, this makes sense :). Why not answer? – joro Mar 24 '15 at 8:25

Let $A$ be the original matrix and $B$ the (0,1) matrix.
Working modulo $n$, it might happen $perm(A)=0$ and perm $perm(B)=mn$.
Though equality holds modulo $n$, $B$ have cycle covers.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.4521193206310272, "perplexity": 786.5943078614524}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2019-30/segments/1563195526386.37/warc/CC-MAIN-20190719223744-20190720005744-00473.warc.gz"}