Quadratically Constrained Reformulation, Strong Semidefinite Programming Bounds, and Algorithms for the Chordless Cycle Problem

Abstract

Given a connected undirected graph $G = (V,E)$, let G[S] be the subgraph of G induced by the set of vertices $S \subseteq V$. The Chordless Cycle Problem (CCP) consists in finding a subset $S \subseteq V$ of maximum cardinality such that G[S] is a chordless cycle. We present a Quadratically Constrained reformulation for the CCP, derive a Semidefinite Programming (SDP) relaxation for it and solve that relaxation by Lagrangian Relaxation (LR). Compared to previously available dual bounds, our SDP bounds resulted to be quite strong. We then introduce a hybrid algorithm involving two combined phases: the LR scheme, which acts as a warm starter for a Branch-and-cut (BC) algorithm that follows it. In short, the LR algorithm allows us to formulate a finite set of SDP cuts that can be used to retrieve the SDP bounds in a Linear Programming relaxation for the CCP. Such cuts are not ready to be used by the BC as they are formulated in an extended variable space. Thus, the BC projects them back onto the original space of variables and separates them by solving a Linear Program. On dense input graphs, our proposed BC algorithm, in its current preliminary state of development, already outperforms its competitors in the literature.

A. S. da Cunha—Supported by CNPq grant 305357/2021-2 and FAPEMIG grants CEX - PPM-00164/17 and RED-00119-21.

A. Lucena—Supported by CNPq grant 310185/2021-1.