Exact Solution Algorithms for the Chordless Cycle Problem

A formulation, a heuristic, and branch-and-cut algorithms are investigated for the chordless cycle problem. This is the problem of finding a largest simple cycle for a given graph so that no edge between nonimmediately subsequent cycle vertices is contained in the graph. Leaving aside procedures based on complete enumeration, no previous exact solution algorithm appears to exist for the problem, which is relevant both in theoretical and practical terms. Extensive computational results are reported here for randomly generated graphs and for graphs originating from the literature. Under acceptable CPU times, certified optimal solutions are presented for graphs with as many as 100 vertices.

Automated summary

This article investigates a formulation, a heuristic, and branch-and-cut algorithms for the chordless cycle problem. Extensive computational results show that certified optimal solutions can be obtained for graphs with up to 100 vertices in acceptable CPU times.