# How does the complexity of calculating the Permanent imply the NP completeness of directed 3-cycle cover?

In their paper Two Approximation Algorithms for 3-Cycle Covers of Markus Bläser and Bodo Manthey it is stated that: "...deciding whether an unweighted directed graph has a 3-cycle cover is already NP-complete. This follows from the work of Valiant  (see also Garey and Johnson [7, GT 13])."

However I can't see what of Valiant's paper The Complexity of Computing the Permanent, resp. the simplified version by Ben-Dor and Halevi, should imply the stated NP-completeness; also GT13 Minimum Bottleneck Path Matching of Garey and Johnson seems to have no obvious relation to the stated complexity.

Questions:

• why does the NP-Completeness of deciding the existence of a directed vertex-disjoint cycle cover follow from Valiant's complexity result of calculating the Permanent?
• what is the transformation that demonstrates the equivalence of the Minimum Bottleneck Path Matching and deciding the existence of a directed vertex disjoint 3-cycle cover?

I have already done extensive googling, but could not find anything that could be cited as a proof of the claimed complexity of deciding the existence of a directed vertex-disjoint 3-cycle cover.

## 1 Answer

When I look in Garey and Johnson I find that [GT 13] is PARTITION INTO HAMILTONIAN SUBGRAPHS which is the problem of deciding if a $$3$$-cycle cover exists in a digraph. So, this could be used as a reference for the complexity. Also, Garey and Johnson cited the Valiant paper for this NP-complete problem.

I took a look at the paper by Valiant linked in the question. If I understand correctly the proof of Lemma 3.1 gives the NP-hardness. The proof takes an instance of 3-SAT and constructs a weighted digraph so that the permanent of the adjacency matrix is some constant times the number of solutions of the 3-SAT instance. However, the weights are chosen so that cycle covers with cycles of length 1 or 2 will cancel. Hence, to my understanding the number of solutions to the 3-SAT instance in the number of 3-cycle covers of the digraph. In particular, there is a 3-cycle cover if and only if the formula is satisfiable.

• Thats a very helpful explanation! I will reread Valiant's paper paying more attention to the part you pointed out. – Manfred Weis Oct 21 '19 at 7:19
• I'm glad it was helpful. The construction in the paper is a little vague. It cites  and  where the ideas come from. I assume more details are in those papers, but I cannot find them. – John Machacek Oct 22 '19 at 1:17
• At least I managed to unearth Paul Peter Herrmann's thesis: On Reducibility Among Combinatorial Problems – Manfred Weis Oct 22 '19 at 8:21
• Strangely, L.G. Valiant's own cited 1974 paper  "A polynomial time reduction of satisfiability to Hamiltonian circuits that preserves the number of solutions" doesn't even appear on his own list of publications – Manfred Weis Oct 22 '19 at 8:36
• Good find with the thesis. That other Valiant paper is cite as "manuscript" maybe it never made it further. – John Machacek Oct 22 '19 at 14:30