3
$\begingroup$

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.

$\endgroup$
1
4
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thats a very helpful explanation! I will reread Valiant's paper paying more attention to the part you pointed out. $\endgroup$ – Manfred Weis Oct 21 '19 at 7:19
  • $\begingroup$ I'm glad it was helpful. The construction in the paper is a little vague. It cites [23] and [9] where the ideas come from. I assume more details are in those papers, but I cannot find them. $\endgroup$ – John Machacek Oct 22 '19 at 1:17
  • $\begingroup$ At least I managed to unearth Paul Peter Herrmann's thesis: On Reducibility Among Combinatorial Problems $\endgroup$ – Manfred Weis Oct 22 '19 at 8:21
  • $\begingroup$ Strangely, L.G. Valiant's own cited 1974 paper [23] "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 $\endgroup$ – Manfred Weis Oct 22 '19 at 8:36
  • $\begingroup$ Good find with the thesis. That other Valiant paper is cite as "manuscript" maybe it never made it further. $\endgroup$ – John Machacek Oct 22 '19 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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