7
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I think that you are mixing up results for the undirected and for the directed version of the problem. $\endgroup$
    – Gamow
    Commented May 11, 2020 at 21:25
  • $\begingroup$ Now that you have edited your question, could you explain to us why you think that your problem is NP-hard? $\endgroup$
    – Gamow
    Commented May 13, 2020 at 9:58
  • $\begingroup$ Because I have not seen an actual algorithm that can solve this problem in polynomial time. $\endgroup$
    – Ben Bezos
    Commented May 16, 2020 at 11:23
  • $\begingroup$ 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. $\endgroup$
    – Ben Bezos
    Commented May 16, 2020 at 11:29

1 Answer 1

Reset to default
23
$\begingroup$

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).

Improve this answer
$\endgroup$
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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