[Solved]: Longest cycle in a digraph

Problem Detail: 

Given a directed graph $G$, we want a (simple) cycle in $G$ of maximal length. The cycle does not need to be an induced subgraph of $G$. What is known about this optimization problem?

Do we know its complexity? Is it much harder than the decision problem of detecting a Hamiltonian cycle? How well-approximable is the problem?

For the exact problem, is there a more efficient algorithm than exhaustive search using Johnson's cycle-enumeration algorithm?

Ideally, for the complexity question, I would like a description similar to here and here for related problems on undirected graphs: Longest induced cycle, Longest path, and Longest induced path. Longest cycle (for undirected graphs) is discussed in "A Structural Overview of NP Optimization Problems", although I have a harder time understanding that account.

FWIW, I'm particularly interested in (approximate) solutions for strongly connected digraphs of 100-500 vertices having average vertex degree ~10 and several induced tournaments on 5-10 vertices. I've been playing with genetic algorithms, and I'd like to know (1) whether better methods are available and (2) what level of performance I can reasonably aim for.

Asked By : Chris Culter

Answered By : Ricky Demer

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51017

 Ask a Question

 Download Related Notes/Documents