In their paper [Two Approximation Algorithms for 3-Cycle Covers](http://wwwhome.math.utwente.nl/~mantheyb/conferences/APPROX2002_BlaeserManthey_3CycleCovers.pdf) 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 [16] (see also Garey and Johnson [7, GT 13])."* 


However I can't see what of Valiant's paper [The Complexity of Computing the Permanent](https://core.ac.uk/download/pdf/82500417.pdf), resp. the [simplified version](https://shaih.github.io/pubs/01perm.pdf) 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.



How does the complexity of calculating the Permanent imply the NP completeness of directed 3-cycle cover?
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.


