minimum degree at least $\alpha n$ has a cycle of length at least $n - C$ is NP-complete.

For part (i), it is known that the problem of determining Hamiltonicity of $3$-regular graphs is NP-complete [@garey1976planar]. Fix $C$ even with $C \geq 4$. Given a $3$-regular graph $G$, let $H$ be the disjoint union of $G$ with an arbitrary $3$-regular graph on $C$ vertices and assume $H$ has $n$ vertices. Then $G$ has a Hamilton cycle if and only if $H$ has a cycle of length at least $n-C$ and so a polynomial-time algorithm for the problem in part (i), for $C$ even and at least $4$, would give a polynomial-time algorithm for deciding Hamiltonicity in $3$-regular graphs.

For the remaining cases of $C$, given a $3$-regular graph $G$, consider the $3$-regular graph $G'$ on $3|V(G)|$ vertices obtained from $G$ by replacing each vertex of $G$ with a triangle in such a way that we recover $G$ by contracting each triangle to a vertex. It is not hard to see that the following are equivalent:

-   $G$ has a Hamilton cycle;

-   $G'$ has a Hamilton cycle;

-   $G'$ has a cycle of length $|V(G')| - 1$;

-   $G'$ has 