<p>Looks like the misunderstanding is this:</p>

<p>In the final reduction to (0,1)-permanent they are using modular
arithmetic, which breaks my argument.</p>

<p>Let $A$ be the original matrix and $B$ the (0,1) matrix.</p>

<p>Working modulo $n$, it might happen $perm(A)=0$ and perm $perm(B)=mn$.</p>

<p>Though equality holds modulo $n$, $B$ have cycle covers.</p>

<hr>

<p>Haven't found the flaw in the question about maximum weighted
cycle cover, which doesn't appear to be affected by the above.</p>

CC BY-SA 3.0
2015-03-26T07:40:55.333Z
2015-03-26T07:40:55.333Z
joro
<p>This confuses me.</p>

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

<p><a href="http://www.cs.cornell.edu/courses/CS6820/2012sp/Handouts/138-150.pdf" rel="nofollow">A lecture</a> 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.</p>

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

<p>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$.</p>

<p>Using gadget they leave only the "good" cycles.</p>

<p>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.</p>

<blockquote>
  <p>What am I misunderstanding?</p>
</blockquote>

<hr>

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

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

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

<p><strong>Edit</strong> <a href="https://mathoverflow.net/questions/172909/reduction-from-permanent-to-0-1-permanent-and-implication-of-p-ne-np">Related MO question</a></p>

<hr>

<p><strong>Added</strong></p>

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

<p>Appears to me the weight of bad cycle in
a widget is zero.</p>

<p>From page 148 (11 of the pdf):</p>

<blockquote>
  <p>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</p>
</blockquote>

<p>Another question:</p>

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

<p>In CC every vertex must be in exactly one cycle.</p>

CC BY-SA 3.0
2014-06-28T11:26:31.577Z
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
CC BY-SA 3.0
2014-06-28T11:31:54.553Z
@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
CC BY-SA 3.0
2014-06-28T11:42:09.323Z
@Saeed Aren't they counting **all** cycle covers in the transformed G'?
joro
CC BY-SA 3.0
2014-06-28T11:43:07.553Z
I think your problem is this. They actually didn't eliminated bad cycles, they eliminated counting them, so they didn't count number of good cycles, they just provide a mapping. But maybe eliminating bad cycles is same as counting good cycle but this is the thing that we cannot do it right now. P.S: About your second question, No, they just provide a mapping between two counting problem nothing more.
Saeed
CC BY-SA 3.0
2014-06-28T11:55:47.130Z
@Saeed Why "mapping"? I interpret it as reduction to counting all cycle covers as stated in the paper, well might be wrong.
joro
CC BY-SA 3.0
2014-06-28T12:01:43.917Z
This is from the text (start of 146) : "Thus we would like to count only the good cycle covers of H", not all cycle cover, they explained in the rest how this works and we can eliminate #bad cycle covers from #cycle covers by counting argument to obtain #good cycle covers. If you have the #cycle covers then you can obtain #good cycle covers. But because there is mapping between number of good cycles and k-VC we cannot. (in above text, #= number of)
Saeed
CC BY-SA 3.0
2014-06-28T12:17:49.497Z
@Saeed Indeed and shortly after they write "The permanent will then count the number of good cycle covers." in their final G'. The permanent of the adj. matrix counts **all** cycle covers.
joro
CC BY-SA 3.0
2014-06-28T12:26:37.593Z
Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/15409/discussion-between-saeed-and-joro).
Saeed
CC BY-SA 3.0
2014-06-29T12:24:38.523Z
Related MO question:  https://mathoverflow.net/questions/172909/reduction-from-permanent-to-0-1-permanent-and-implication-of-p-ne-np
joro
CC BY-SA 3.0
2015-03-24T08:21:15.973Z
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
CC BY-SA 3.0
2015-03-24T08:25:20.480Z
@MarkusBläser Thank you, this makes sense :). Why not answer?
joro
CC BY-SA 3.0
2015-03-24T09:13:01.773Z
@MarkusBläser Wouldn't finding maximum weight cycle cover correspond to vertex cover in the original graph?
joro
CC BY-SA 3.0
2015-03-24T11:40:13.317Z
@MarkusBläser Don't widgets contribute zero for bad cycle? From p.14 "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 badcycle cover**.
joro
<cc.complexity-theory><graph-theory>
Confusion about reduction counting vertex covers to counting cycle covers
joro
# Confusion about reduction counting vertex covers to counting cycle covers

(Asked by: username_0 on 2014-06-28)

This confuses me.

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

[A lecture](http://www.cs.cornell.edu/courses/CS6820/2012sp/Handouts/138-150.pdf) 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$.

**Edit** [Related MO question](https://mathoverflow.net/questions/172909/reduction-from-permanent-to-0-1-permanent-and-implication-of-p-ne-np)

---

**Added**

`username_2` 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.

**Tags:** cc.complexity-theory, graph-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1 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$.  
> **username_0**: @username_1 Aren't they counting **all** cycle covers in the transformed G'?  
> **username_1**: I think your problem is this. They actually didn't eliminated bad cycles, they eliminated counting them, so they didn't count number of good cycles, they just provide a mapping. But maybe eliminating bad cycles is same as counting good cycle but this is the thing that we cannot do it right now. P.S: About your second question, No, they just provide a mapping between two counting problem nothing more.  
> **username_0**: @username_1 Why "mapping"? I interpret it as reduction to counting all cycle covers as stated in the paper, well might be wrong.  
> **username_1**: This is from the text (start of 146) : "Thus we would like to count only the good cycle covers of H", not all cycle cover, they explained in the rest how this works and we can eliminate #bad cycle covers from #cycle covers by counting argument to obtain #good cycle covers. If you have the #cycle covers then you can obtain #good cycle covers. But because there is mapping between number of good cycles and k-VC we cannot. (in above text, #= number of)  
> **username_0**: @username_1 Indeed and shortly after they write "The permanent will then count the number of good cycle covers." in their final G'. The permanent of the adj. matrix counts **all** cycle covers.  
> **username_1**: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/15409/discussion-between-saeed-and-username_0).  
> **username_0**: Related MO question:  https://mathoverflow.net/questions/172909/reduction-from-permanent-to-0-1-permanent-and-implication-of-p-ne-np  
> **username_2**: 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.  
> **username_0**: @MarkusBläser Thank you, this makes sense :). Why not answer?  
> **username_0**: @MarkusBläser Wouldn't finding maximum weight cycle cover correspond to vertex cover in the original graph?  
> **username_0**: @MarkusBläser Don't widgets contribute zero for bad cycle? From p.14 "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 badcycle cover**.  

---

## 1 answers

### Answer by username_0 on 2015-03-26. Score: 1

Looks like the misunderstanding is this:

In the final reduction to (0,1)-permanent they are using modular
arithmetic, which breaks my argument.

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.

---

Haven't found the flaw in the question about maximum weighted
cycle cover, which doesn't appear to be affected by the above.


---

