A column generation algorithm for finding co-3-plexes in chordal graphs Journal: Discrete optimization

Alexandre Dupont-Bouillard · 2026

Read A column generation algorithm for finding co-3-plexes in chordal graphs Journal: Discrete optimization by Alexandre Dupont-Bouillard (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-00721.txt.

Introduction

Dupont-Bouillard tackles co-3-plexes in chordal graphs. A co-3-plex is a vertex subset inducing a subgraph of degree at most 2. Since chordal co-3-plexes induce triangles and induced paths, he reduces the search to maximum stable set search in an auxiliary graph of exponential size. That yields a variable-sized linear programming formulation for maximum weighted co-3-plexes. The pricing subproblem reduces to a maximum vertex-edge weight induced path problem, solvable in polynomial time.

Catalog record

CREATORAlexandre Dupont-Bouillard
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22398
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.00721

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A column generation algorithm for finding co-3-plexes in chordal graphs Journal: Discrete optimization Alexandre Dupont-Bouillard Abstract In this study, we tackle the problem of finding a maximum 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 G to that of finding a maximum stable set in an auxiliary graph 𝒜 ⁡ ( G ) \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. Keywords— co- k k -plex extended formulations co-3-plex polytope chordal graphs, column generation. Definitions All graphs in this article are simple and connected unless specified. Given a graph G=(V,E) , we denote its complement by \overline{G}=(V,\overline{E}) , where \overline{E}=\{e\in\binom{V}{2}:e\notin E\} . We respectively denote by V(G) and E(G) the vertex set and the edge set of G . Two vertices u and v are adjacent if uv\in E(G) . Given a subset of vertices W\subseteq V , let E(W) denote the set of edges of G with both endpoints in W and \delta(W) denote the set of all edges with exactly one endpoint in W . When W is a singleton \{w\} , we will write \delta(w) . We say that the edges in \delta(w) are incident to w , and two edges sharing an extremity are said to be adjacent . For F\subseteq E , let V(F) denote the set of vertices incident to any edge in F . Given W\subseteq V , the graph G[W]=(W,E(W)) is the subgraph of G induced by W . When H is an induced subgraph of G , we say that G contains H . Given a vertex u\in V(G) , we denote by N_{G}(u)=\{w\in V(G):uw\in E(G)\} its neighborhood , and by N_{G}[u]=N_{G}(u)\cup\{u\} its closed neighborhood , when clear from context we simply write N(u) and N[u] . Two vertices u and v are true twins if N[u]=N[v] and false twins if N(u)=N(v) . A vertex is simplicial if its neighborhood induces a clique. A subset K of vertices is a k -plex (resp. co- k -plex ) if G[K] has minimum degree |K|-k (resp. maximum degree k-1 ). Note that k -plexes are complements of co- k -plexes. Cliques are 1 -plexes and stable sets are co-1-plexes. We denote by \mathcal{K}(G) the set of inclusion-wise maximal cliques of G . An induced path (resp. hole ) is a graph induced by a sequence of vertices (v_{1},\dots,v_{p}) whose edge set is \{v_{i}v_{i+1}:\ i=1,\dots,p-1\} (resp. \{v_{i}v_{i+1}:\ i=1,\dots,p-1\}\cup\{v_{1}v_{p}\} ). A subset of vertices induces a path (resp. hole) if its elements can be ordered into a sequence inducing a path (resp. hole). The length of a path or hole is its number of edges. The parity of a path or hole is the parity of its length. The contraction of an edge uv\in E(G) yields a new graph G/uv built from G by deleting u and v , adding a new vertex w , and adding the edges wz for all z\in(N_{G}(u)\cup N_{G}(v))\setminus\{u,v\} . For F\subseteq E , we denote by G/F the graph obtained from G by contracting all edges in F . A graph is t -chordal if its holes have maximum size t ; 3-chordal graphs are called chordal . Let \mathcal{P}=\{x:Ax\leq b\}\subseteq\mathds{R}^{n} be a polyhedron , that is, the intersection of finitely many half-spaces. The dimension of \mathcal{P}\subseteq\mathds{R}^{n} , denoted by dim \mathcal{P} , is the maximum number of affinely independent points in \mathcal{P} minus one. If a\in\mathds{R}^{n}\setminus\{0\} , \alpha\in\mathds{R} , then the inequality a^{\top}x\leq\alpha is said to be valid for \mathcal{P} if \mathcal{P}\subseteq\{x\in\mathds{R}^{n}:a^{\top}x\leq\alpha\}. The polyhedron \mathcal{P}\subseteq\mathds{R}^{n} is full-dimensional when dim \mathcal{P} is equal to n . Extreme points of a polyhedron are its faces of dimension zero. Each extreme point satisfies \textrm{dim}~\mathcal{P} linearly independent valid inequalities for \mathcal{P} with equality. A polyhedron \mathcal{P}\subseteq\mathds{R}^{n} is said to be integer if all its non-empty faces contain an integer point. A polytope is a bounded polyhedron, equivalently, it can be defined as the convex hull of a finite number of points P and is denoted by \textrm{conv}(P) . A 0/1 minimal squared submatrix of odd size having two ones per row and per column is called an odd hole and has a determinant of two. Given x variables on the vertices of a graph G , an important ingredient for our proof is the following theorem characterizing the perfectness of a graph by the hyperplane representation of the convex hull of its stable sets’ incidence vectors, that is its stable set polytope . Note that we will not use the historical definition of perfect graphs, which requires equality between the coloring number and clique number for each induced subgraph. Theorem 1 ( [ 3 ] ) . A graph G is perfect if and only if its stable set polytope is described as follows: \displaystyle x(K)\leq 1 \displaystyle\forall K\in\mathcal{K} (1) \displaystyle x_{u}\geq 0 \displaystyle\forall u\in V (2) Note that odd holes are not perfect, nor are their complement; these two types of induced subgraphs are the ones to be forbidden to describe perfect graphs, as stated in the strong perfect graphs theorem [ 2 ] . Motivations The problem of finding "communities" in a network arises in social network analysis, notably for the recognition of cohesive subgroups. The most natural graph notion one could think of to describe such a group is a clique; however, asking that all pairs of vertices are adjacent may be too restrictive. Therefore, several relaxed clique definitions have been proposed; see [ 13 ] for a survey. One type of such relaxed cliques is called a k -plex, and finding a maximum weighted such subset of vertices is NP-hard [ 1 ] . By complementing the input graph, the problem of finding a maximum weighted co- k -plex is also. This problem (or rather its complement) has been widely studied from an experimental point of view [ 12 , 13 , 1 , 14 , 4 , 15 , 9 ] . The case k=2 has also been studied from a polyhedral point of view in natural variable space [ 11 ] and extended variable space [ 6 ] , permitting to describe the polytope of contraction perfect graphs [ 5 ] and holes. It is precisely at this point that new connected structures appear: components of a co-3-plex may be induced paths or holes, in contrast to the isolated vertices and edges arising for co-2-plexes. Asking whether extended formulations can still be obtained from perfect graphs is a natural and fundamental question. This work studies

Read the complete text