$G$ respresents an undirected graph and a cycle refers to a simple cycle (no repeated edges or vertices).
Define the following two languages.
$\text{SCYCLE}=\{(G,k)\mid G \text{ contains a cycle of length at most k}\}$
and
$\text{LCYCLE}=\{(G,k)\mid G \text{ contains a cycle of length at least k}\}$
Which of the following is NOT known to be TRUE (to the best of our current knowledge) ?
- $\text{SCYCLE} \in P$
- $\text{LCYCLE} \in NP.$
- $\text{LCYCLE} \leq_{p} \text{SCYCLE}$ (i.e, there is a polynomial time many-to -one reduction
from $\text{LCYCLE}$ to $\text{SCYCLE}$).
- $\text{LCYCLE}$ is NP-complete.
- $\text{SCYCLE} \leq_{p} \text{LCYCLE}$ (i.e, there is a polynomial time many-to-one reduction
from $\text{SCYCLE}$ to $\text{LCYCLE}$).