6
$\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])."

Garey&Johnson GT13

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.

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?

A direct proof via a reduction from 3D matching can be found in Computing Cycle Covers without Short Cycles

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
6
$\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.

Improve this answer
$\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
    Commented Oct 21, 2019 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
    Commented Oct 22, 2019 at 1:17
  • $\begingroup$ At least I managed to unearth Paul Peter Herrmann's thesis: On Reducibility Among Combinatorial Problems $\endgroup$
    – Manfred Weis
    Commented Oct 22, 2019 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
    Commented Oct 22, 2019 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
    Commented Oct 22, 2019 at 14:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .