By querying for a cycle of each length, your problem is in FP||FNP.
The following is a reduction from FP||FNP to your problem,
If there are no queries then just compute the output. If there's exactly one query then Connect up the paths (search for "Connecting up"). Otherwise, for each query, for the CNF-SAT instance representing that query, create a new variable, put that variable into each clause, and create a new clause with just the negation of that variable. Connect up the paths, but instead of putting in the magenta edge on those pages, string those graphs together cyclically by merging each t vertex with an s vertex (from a different query). For each s-t portion, if the cycle traverses the
[variable that wasn't originally in the corresponding CNF-SAT instance] in the False direction,
then [the truth values encoded by its directions along the s-t portion's other chains]
are a witness for the corresponding query, else there are no witnesses for
the corresponding query. Use the resulting witnesses to compute the output.
since
a [cycle that doesn't use any s-t vertex] must stay within a single s-t portion,
whereas a cycle that uses the s-t vertices in their cyclic order can use all of them
and all-but-at-most-one from each s-t portion, so if there's more than one query
then cycles that don't use any s-t vertex can't be longest cycles
and
a cycle that uses at least one s-t vertex must use them all,
so it must use as many vertices as possible in each s-t portion
and
for each s-t portion, if the original CNF-SAT representing the corresponding query is satisfiable then there's a path through that portion which uses all of its vertices, else there's
a path through that portion which uses all but one of those vertices (traverse the
[variable that wasn't originally in the CNF-SAT instance] in the False direction)
.
(Thus, your problem is FP||FNP-complete.
That reduction goes FP||FNP -> MAX-SAT -> your problem .)
For approximation, this is the main paper, although I'm annoyed
at how they very-nearly show things but don't state them.
Since for a fresh variable h, R($\hspace{.02 in}$g,h,g) will force g to be False, and then such g
can be used everywhere, including in R(+x,g,-x) constraints to force +x and -x
to take on opposite truth values, wikipedia's formula induces a reduction from
m-clause n-variable 3-SAT to ((5$\hspace{-0.02 in}\cdot \hspace{-0.02 in}$m)+n+1)-clause ((6$\hspace{-0.02 in}\cdot \hspace{-0.02 in}$m)+(2$\hspace{-0.02 in}\cdot \hspace{-0.02 in}$n)+2)-variable monotone 1-in-3 SAT.
By digging through section 7 ("Proof of Proposition 1"), one can see that they have a reduction from the search version of m-clause n-variable monotone 1-in-3 SAT to the search version of
((145$\hspace{-0.02 in}\cdot \hspace{-0.02 in}$m)+n+2)-vertex R2VDP with in-degree and out-degree both bounded by 3 which works even if some clause(s) has(ve) more than one of the same variable. (If I'm wrong about the last part
of my previous sentence, then one can just replace R($\hspace{.02 in}$g,h,g) with R(u,g,v) ∧ R(u,v,w) ∧ R(v,g,w) .)
Since one can [$\hspace{.03 in}$just output a cycle for sizes that are at most 3$\hspace{-0.02 in}\cdot \hspace{-0.02 in}$v] and [replace the 2->3 edges
along the bottom of figure 1 with paths that each have at most 2$\hspace{-0.02 in}\cdot \hspace{-0.02 in}$v internal vertices],
figure 1 (with each G a copy of the input instance) yields [a reduction from v-vertex R2VDP to digraphs whose number of vertices is at least three but otherwise arbitrary] such that, given a
full solution to the R2VDP instance (i.e., one that exhausts all the vertices) one can efficiently
find a Hamiltonian cycle in the output graph, and given [a cycle in the output graph whose
length exceeds 3$\hspace{-0.02 in}\cdot \hspace{-0.02 in}$v] one can efficiently find a not-necessarily-full solution to the R2VDP instance.
Clearly, only the last of the previous paragraph's three sentences (the really-long one) might
yield any meaningful concrete lower bounds for your input sizes. However, one can alternatively reduce from [the modification of 2VDP to promise that if there are any such pairs of paths then there is such a pair of paths that together use enough of the vertices] at the cost of replacing ["Hamiltonian cycle" with "cycle that uses enough of the vertices"] and ["full" with "full-enough"].
In the positive direction:
That paper also [references an algorithm that you should consider]
and [gives an algorithm that you should consider].
You can find both of those by going to the bottom paragraph on the page before section 2.
Color-coding can efficiently find short-enough cycles. This paper's algorithm can more-efficiently
find short-enough paths, and it seems plausible that either it or one of the algorithms it
references can be modified to find short-enough cycles more efficiently than color-coding.
