2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

The problem of finding a longest simple cycle in a digraph is NP-hard, since the problem of finding a longest simple cycle in an undirected graph is a special case: you can consider an undirected graph to be a digraph with a symmetric edge relation. (Longest simple cycle is NP-hard since it lets you solve Hamiltonian cycle.)

$\endgroup$
  • $\begingroup$ The problem of hamiltonian cycle (and path) in directed graphs is NP-complete, all by itself. $\endgroup$ – vonbrand Aug 29 at 12:57
  • 1
    $\begingroup$ Well, sure, but the problem is usually stated for undirected graphs. The reduction is trivial so I figured I may as well say what it was, rather than just assert its existence. $\endgroup$ – David Richerby Aug 29 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.