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