  An edge-coloured cycle is $rainbow$ if all edges of the cycle have distinct
colours. For $k\geq 1$, let $\mathcal{F}_{k}$ denote the family of all graphs
with the property that any $k$ vertices lie on a cycle. For $G\in
\mathcal{F}_{k}$, a $k$-$rainbow$ $cycle$ $colouring$ of $G$ is an
edge-colouring such that any $k$ vertices of $G$ lie on a rainbow cycle in $G$.
The $k$-$rainbow$ $cycle$ $index$ of $G$, denoted by $crx_{k}(G)$, is the
minimum number of colours needed in a $k$-rainbow cycle colouring of $G$. In
this paper, we restrict our attention to the computational aspects of
$k$-rainbow cycle colouring. First, we prove that the problem of deciding
whether $crx_1=3$ can be solved in polynomial time, but that of deciding
whether $crx_1 \leq k$ is NP-Complete, where $k\geq 4$. Then we show that the
problem of deciding whether $crx_2=3$ can be solved in polynomial time, but
those of deciding whether $crx_2 \leq 4$ or $5$ are NP-Complete. Furthermore,
we also consider the cases of $crx_3=3$ and $crx_3 \leq 4$. Finally, We prove
that the problem of deciding whether a given edge-colouring (with an unbounded
number of colours) of a graph is a $k$-rainbow cycle colouring, is NP-Complete
for $k=1$, $2$ and $3$, respectively. Some open problems for further study are
mentioned.
