A column generation algorithm for finding co-3-plexes in chordal graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911559767293952 |
|---|---|
| author | Dupont-Bouillard, Alexandre |
| author_facet | Dupont-Bouillard, Alexandre |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_00721 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A column generation algorithm for finding co-3-plexes in chordal graphs Dupont-Bouillard, Alexandre Data Structures and Algorithms Discrete Mathematics 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. |
| title | A column generation algorithm for finding co-3-plexes in chordal graphs |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2604.00721 |