I've read in multiple articles and books that the computation of a cycle cover for a given graph is possible in polynomial time, since this problem can be viewed as the assignment problem, which is a special type of matching problem. It's written in the Algorithmic Aspects of Bioinformatics (Spring-2007) and in the Minimum-weight Cycle Covers and Their Approximability by Bodo Manthey. I failed to find any article, page or book explaining how is it possible to view the computation of cycle cover as an assignment problem. It seems impossible to me, since the assignment problem is about bipartite graphs, and the cycle cover is about finding a spanning subgraph in a complete graph.

  • 1
    $\begingroup$ If every vertex chooses a neighbor and you take all these edges together, you get a cycle cover. $\endgroup$ – Yuval Filmus Apr 26 '17 at 21:10
  • $\begingroup$ I'm sorry, I don't see your point. Could you please give some more details? "If every vertex chooses a neighbour" In a bipartite graph or in a complete graph? How would choosing neighbours give a cycle cover? $\endgroup$ – Supercat Apr 26 '17 at 21:29
  • $\begingroup$ Try it out on an example and see what happens. Note that you can also get cycles of length 2. $\endgroup$ – Yuval Filmus Apr 26 '17 at 21:30

Your Answer

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

Browse other questions tagged or ask your own question.