A column generation algorithm for finding co-3-plexes in chordal graphs

View PDF HTML (experimental)

Abstract:In this study, we tackle the problem of finding a maximum \emph{co-3-plex}, which is a subset of vertices of an input graph, inducing a subgraph of maximum degree 2. We focus on the class of chordal graphs. By observing that the graph induced by a co-3-plex in a chordal graph is a set of isolated triangles and induced paths, we reduce the problem of finding a maximum weight co-3-plex in a graph $G$ to that of finding a maximum stable set in an auxiliary graph $\mathcal{A}(G)$ of exponential size. This reduction allows us to derive an exponential variable-sized linear programming formulation for the maximum weighted co-3-plex problem. We show that the pricing subproblem of this formulation reduces to solving a maximum vertex and edge weight induced path. Such a problem is solvable in polynomial time; therefore, this exhibits a polynomial time column generation algorithm solving the maximum co-3-plex problem on chordal graphs. Moreover, this machinery exhibits a new application for the maximum vertex and edge weighted induced path problems.

Subjects:

Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)

Cite as: arXiv:2604.00721 [cs.DS]

(or arXiv:2604.00721v1 [cs.DS] for this version)

https://doi.org/10.48550/arXiv.2604.00721

arXiv-issued DOI via DataCite (pending registration)

Submission history

From: Alexandre Dupont-Bouillard [view email] [v1] Wed, 1 Apr 2026 10:31:47 UTC (41 KB)