11
$\begingroup$

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

Edit Related MO question

Added

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.

Improve this question
$\endgroup$
13
  • $\begingroup$ 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. $\endgroup$
    – Saeed
    Jun 28, 2014 at 11:26
  • $\begingroup$ @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$. $\endgroup$
    – joro
    Jun 28, 2014 at 11:31
  • $\begingroup$ @Saeed Aren't they counting all cycle covers in the transformed G'? $\endgroup$
    – joro
    Jun 28, 2014 at 11:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – Markus Bläser
    Mar 24, 2015 at 8:21
  • 1
    $\begingroup$ @MarkusBläser Thank you, this makes sense :). Why not answer? $\endgroup$
    – joro
    Mar 24, 2015 at 8:25

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.