Exact Solution Algorithms for the Chordless Cycle Problem

Dilson Lucas Pereira (), Abilio Lucena (), Alexandre Salles da Cunha () and Luidi Simonetti ()
Additional contact information
Dilson Lucas Pereira: Departamento de Computação Aplicada, Universidade Federal de Lavras, Lavras, Caixa 3037, CEP 37200-900, Brazil
Abilio Lucena: Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Caixa 68511, CEP 21941-972, Brazil
Alexandre Salles da Cunha: Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Belo Horizonte, CEP 31270-901 Brazil
Luidi Simonetti: Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Caixa 68511, CEP 21941-972, Brazil

INFORMS Journal on Computing, 2022, vol. 34, issue 4, 1970-1986

Abstract: 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. Summary of Contribution: Finding chordless cycles of a graph, also known as holes, is relevant, among others, to graph theory, to the design of polyhedral based exact solution algorithms to integer programming (IP) problems, and to the practical applications that benefit from these algorithms. For instance, perfect graphs do not contain odd holes. Additionally, odd hole inequalities are valid for strengthening the formulations to numerous problems that are directly defined over graphs. Furthermore, these inequalites, in association with applicable conflict graphs, are used by all modern IP solvers to preprocess and strengthen virtually any IP formulation submitted to them.

Keywords: induced subgraphs; chordless cycles; branch-and-cut algorithms (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1164 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:4:p:1970-1986

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().