7

Given: An undirected, unweighted graph

Looking for: A disjoint vertex cycle cover where every cycle has at least 3 edges

Is there any algorithm that solves this problem, possibly with some heuristics? Can the bipartite representation of the graph used for finding perfect matching be leveraged here?

Ben Bezos
  • 79
  • 4
  • 1
    I think that you are mixing up results for the undirected and for the directed version of the problem. – Gamow May 11 '20 at 21:25
  • Now that you have edited your question, could you explain to us why you think that your problem is NP-hard? – Gamow May 13 '20 at 09:58
  • Because I have not seen an actual algorithm that can solve this problem in polynomial time. – Ben Bezos May 16 '20 at 11:23
  • What I am doing right now is using the Hopcroft–Karp algorithm to obtain a maximum matching on the bipartite representation of the original graph. This maximum matching on the bipartite graph is a cycle cover when mapped to the original graph, but it may contain paths. What I didn't fully understand is if this method gives any guarantee reagrding cycle lengths. – Ben Bezos May 16 '20 at 11:29

1 Answers1

22

The cycle cover problem (CC) is the problem of finding a spanning set of cycles in a given directed or undirected input graph. If all the cycles in the cover must consist of at least $k$ edges/arcs, the resulting restriction of the problem is denoted $k$-UCC (in undirected graphs) and $k$-DCC (in directed graphs).

The complexity of the directed version is fully understood:

  • Markus Bläser and Bodo Siebert ("Computing Cycle Covers without Short Cycles", in Proceedings of ESA 2001, LNCS 2161, pp 368--379) have proved that $k$-DCC is NP-complete for any fixed $k\ge3$.

The complexity landscape of the undirected version is more diverse, and there are some open questions:

  • $3$-UCC is polynomially solvable. This is a folklore result that follows from a reduction of Tutte ("A short proof of the factor theorem for finite graphs", Canadian Journal of Mathematics 6, pp 347–352, 1954) to the classical unrestricted matching problem.

  • David Hartvigsen (in his PhD thesis "An Extension of Matching Theory", Carnegie-Mellon University, 1984) has shown that $4$-UCC is polynomially solvable.

  • The complexity status of $5$-UCC is open. David Hartvigsen has some positive results on special cases of this problem ("The square-free 2-factor problem in bipartite graphs", in Proceedings of IPCO 1999, LNCS 1610, pp 234–241).

  • Papadimitriou has proved that $k$-UCC is NP-complete for any fixed $k\ge6$. His proof is sketched in the 1980 paper "A matching problem with side conditions" by Gerard Cornuejols and Bill Pulleyblank (Discrete Mathematics 29, pp 135--159).

Gamow
  • 5,772
  • 6
  • 25
  • 39