Complexity of Two problems graphs with cycle

Question

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?

Answer 1

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