0

I decided to try implement some assignment problem algorithms. I already did some, but I got stuck on the problem described below:

To put it simply, I need to cover all its vertices with the minimum number of non-intersecting simple cycles.

But I don't understand how, does anyone have any ideas? I would be especially glad to see an explanation.

Improve this question
3
  • Hi! This sounds like the disjoint cycle cover problem. However, I'm not sure about the meaning of "simple" when you say "simple circle". Can you please explain what you mean by "simple"? Do you mean the cycles shouldn't have chords? Commented May 1, 2022 at 18:27
  • As far as I know, simple cycles are closed traversals without revisiting a vertex twice, except for the start and end vertices. Commented May 1, 2022 at 18:32
  • Please provide enough code so others can better understand or reproduce the problem. Commented May 2, 2022 at 1:38

1 Answer 1

Reset to default
0

This problem is NP-hard via a reduction from the Hamiltonian cycle problem. More specifically, if a graph has a Hamiltonian cycle, then you can cover all the vertices with a single simple cycle, namely the Hamiltonian cycle, and otherwise the graph requires multiple cycles to cover its nodes (if it can even be done at all).

As a result, unless P = NP, there are no polynomial-time algorithms for this problem. You can still solve it using either heuristic searches or brute force, but those approaches won’t necessarily be fast on all inputs.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.