2
$\begingroup$

The circumference of a graph is the length of any longest cycle in the graph. The problem of determining circumference of a graph should be NP-complete. However, for graphs of moderate size, is there also a clever brute-force approach?

I referred to the link, where someone mentioned that the Johnson's algorithm is the most efficient. However, I'm not sure about the source of this algorithm or if there's an existing implementation based on it. When it comes to finding the longest cycle, I currently feel that the software Mathematica might be most effective (although there is no direct command for it). As for open-source programs, the one I've come across is the one below, but its efficiency doesn't seem to be notably high.

I once raised this question on the Mathematica stack, and they suggested that I should start by looking for algorithms. Are there any references or surveys on the theory or algorithms related to finding the longest cycle?

$\endgroup$
1
  • 1
    $\begingroup$ Johnson's algorithm is for finding shortest paths, it's not going to be useful in your situation. $\endgroup$
    – Pål GD
    Aug 31, 2023 at 7:35

1 Answer 1

5
$\begingroup$

Unfortunately the following problem is very hard:

Problem: Long Cycle
Input: A graph $G$ and an integer $k$
Question: Does $G$ have a simple cycle of length at least $k$?

The problem is clearly NP-complete as it is a generalization of Hamiltonian Cycle (the problem has a cycle of length at least $n$ if and only if the graph is Hamiltonian).

There is no fast algorithm for this problem, and to the best of my knowledge, the fastest FPT algorithm runs in time $O(4.884^k \cdot n^{O(1)})$ [1].


[1] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi, Long directed (s,t)-path: FPT algorithm, Information Processing Letters, 2018

$\endgroup$
6
  • $\begingroup$ Indeed. If a search for the longest cycle remains effective for graphs with up to 100 vertices, that would be good for me. I just see an article ( doi.org/10.1002/net.3230060206) that formulated it as an integer programming problem. I have not implemented it yet, so I'm unsure about its effectiveness in my examples (about 50 vertices). $\endgroup$
    – licheng
    Aug 31, 2023 at 8:02
  • $\begingroup$ Do you need the absolute longest cycle, or is it enough to find a $k$-cycle? $\endgroup$
    – Pål GD
    Aug 31, 2023 at 8:08
  • 1
    $\begingroup$ You can easily model the $k$-cycle problem as a SAT instance and use off-the-shelf SAT solvers. That could work $\endgroup$
    – Pål GD
    Aug 31, 2023 at 8:08
  • 1
    $\begingroup$ I don't but you can check out The International SAT Competition Web Page and specifically the Glucose SAT solver, which is open source. $\endgroup$
    – Pål GD
    Aug 31, 2023 at 9:34
  • 2
    $\begingroup$ When it comes to encoding your problem as a SAT instance, you simply create "slots" $s_{i, v}$ for each position $i$ in the cycle, and $v$ a vertex in the graph. Then you need to add the constraints that each vertex is in at most one slot, each slot is filled, and for two neighboring slots, they share an edge. I think this is textbook material, so you might find this verbatim if you go look for it. $\endgroup$
    – Pål GD
    Aug 31, 2023 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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