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

@Saeed Aren't they counting all cycle covers in the transformed G'?

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 Why "mapping"? I interpret it as reduction to counting all cycle covers as stated in the paper, well might be wrong.

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

Did you really read my previous comment completely?

Hi

Hi

Yes, I think it is on my side. I claim we have the decision problem "Is permanent of (0,1) matrix zero?" in P. The permanent counts all CC and their G' have only the good cycles. What you wrote appears to me obstacles they overcome.

I don't claim I can count CC, I claim I know they are zero or not.

Suppose they are not zero then how do you want to say there is a VC?

They don't count number of all good cycles, they just prevent from counting number of bad cycle cover in their counting argument

They start from graph G and transform it to digraph G'. G' lacks bad cycle AFAICT. What is the relation between G and G' according to you? (According to me it gives relation between #VC of size k in G to #CC in G'). What is you interpretation?

Sorry I cannot see G' in the lecture note, do you mean H?

OK I see right now

Let me read the G' part

OK, G' is actually nothing special

I think in some sense you are right

the lecture is not correct because should say every cycle cover in H is mapped by some weighted cycle cover in G'

Sorry each weighted cycle cover in H is mapped by some cycle cover on G'

covers*

G' is on p.13 of the PDF.

I saw it

Their argument is correct but in the last part they made typo

AFAICT H is the first step. In the second step using gadgets they get G' which is bad free.

Yes I read a little bit through their gadget then I didn't read the part about counting argument and I supposed is correct

so I didn't see the last page

RE weighted - they are removing weights by adding edges and vertices on p.13

The last page seems to be wrong (typo IMO)

yes I see

What is typo?

In the last page their conclusion is totally nonsense

This is possible, though I don't find it very likely.

"Each cycle cover in G involving edges ui vi with weights mi  i n is simulated by mm mn cycle covers in G each of weight 1"

This is totally nonsense (or I should read their construction in detail)

Cycle cover in G does not have to do anything with vertex cover in G

I think this is explained by the drawing of edge with weight 3 on p. 13

They should map it to H

not to G

suppose we count all cycle covers On G

then what we want to say about vertex cover on G?

There was a mapping (reduction) between #good cycle covers in H and #vertex covers in G

So G' is actually maps to all cycle covers in H not G

(Actually weighted H)

They transform H with gadgets (the matrix stuff) to kill bad cycles in G' AFAICT.

Yes, but then the last sentence is totally nonsense, what's a relation of a cycle cover between G and G'? What does this implies? Nothing.

There is no relation of cycle cover between G and G'. There is relation #VC and #CC (since #VC is #P-complete) and this way the prove #CC is #P-complete IMHO.

Does this make sense to edit the question, suggestion, improvements?

EDIT:

OK, the lecture might be wrong. What about the suggested edit?

I think they mean: "to get rid of the weights, we simulate them with gadgets while keeping the permanents the same".

I'm actually stressing on " Each cycle cover in G ". Not about gadget or weights or permanent.

This seems to be typo

About your edit to the question

I think still their argument is same and does not violate anything

I'll read the original paper and will talk later.

OK. Thank you.

So you disagree with both me and the paper?

yes