**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

## 0 comments:

## Post a Comment

Let us know your responses and feedback