1
$\begingroup$

I want to determine the complexity of these two problems (with a given k):

1) Determine if the graph G has a cycle of length less or equal than k;

2) Determine if the graph G has a cycle of length equal or more than k.

For the first problem, I think it is NP-complete because it is NP (but why?) and because we can reduce the HAM-CYCLE problem to it (but how?)

I don't know what to say about the second problem. Can you help me solving this and can you help me telling me what is a good method to solve these kind of problems?

$\endgroup$
2
$\begingroup$

The first problem can be answered by finding the length of the shortest cycle in $G$, a parameter known as the girth of $G$. Indeed, if $G$ has girth $g$ then $G$ contains a cycle of length at most $k$ iff $g \leq k$. You can use BFS to find the girth efficiently, see for example these course notes. Therefore this problem can be solved in polynomial time.

The second problem is NP-complete by reduction from Hamiltonian cycle, as you mention (just choose $k = n$).

$\endgroup$
  • $\begingroup$ my problem is that I don't know how to write that reduction. Anyway, thank you for the answer $\endgroup$ – kdpkke Feb 8 '18 at 20:55

Your Answer

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

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