K-Hole Separation in PEO-Based ILP Treewidth Formulation

Many hard combinatorial graph problems become (sometimes trivially) polynomially solvable when the input is restricted to trees. This naturally raises the question of how far a general graph $G=(V,E)$ is from being a tree. In their seminal work [37], Robertson and Seymour introduced the concepts of tree decomposition and treewidth. The latter is a graph invariant that provides a quantitative answer to this question¹¹1Interestingly, despite its important algorithmic implications, Robertson and Seymour did not originally develop treewidth with algorithms in mind. Readers curious about the origin of the concept may consult Seymour’s explanation on this blog post [38]..

The most common definition of tree decomposition of an unweighted, undirected simple graph $G=(V,E)$ is the following.

The width of a tree decomposition $(T,{(B_x)}_{x\in V(T)})$ is ${\max }_{x\in V(T)}(|B_x|-1)$. The treewidth $\text{tw}(G)$ of a graph $G$ equals to the minimum width over all the tree decompositions of $G$. The minus one adjustment ensures that trees have width one. On the other hand, the complete graph on $n$ vertices has treewidth equal to $n-1$.

From a computational perspective, deciding the treewidth of a graph is an $𝒩𝒫$-complete problem. Nonetheless, many ($𝒩𝒫$-hard) problems on graphs can be solved efficiently on instances of bounded treewidth [6, 8, 16, 18, 11].

Two relevant computational paradigms to exactly compute the treewidth of a graph have emerged from the PACE challenges in 2016 and 2017 [12, 13]. Here, both Tamaki’s dynamic programming approach [40] and Bannach, Bernds, and Ehlers’ SAT approach based on perfect elimination orderings (PEOs) [2] proved particularly successful. PEOs and treewidth are in fact closely related. Koster and Bodlaender proposed the first integer linear programming (ILP) formulation for treewidth based on the vertex elimination order and the connection between the treewidth and the triangulation of the graph (see both [7, 21]). Indeed, the notion of treewidth admits equivalent definitions, one of which is based on such concepts.

A graph $G=(V,E)$ is chordal if and only if each cycle in $G$ of length at least four has a chord, i.e., an edge between non-consecutive vertices in the cycle. A perfect elimination order (or scheme) of an $n$-vertex graph $G=(V,E)$ is a bijection of the vertices $\pi :V\to 1,\mathrm{\dots },n$, such that, for all $v_i\in V$, its higher ordered neighbours form a clique, i.e., for $\pi (v_{j_1})>\pi (v_i)$, $\pi (v_{j_2})>\pi (v_i)$, if $\{v_i,v_{j_1}\}\in E$ and $\{v_i,v_{j_2}\}\in E$, then $\{v_{j_1},v_{j_2}\}\in E$. A triangulation (or chordal completion) of $G$ is a chordal graph $H=(V,F)$ that contains $G$ as a subgraph: $E\subseteq F$. A triangulation $H=(V,F)$ is a minimal triangulation when there does not exist a triangulation $H^{\prime }=(V,F^{\prime })$ with $E\subseteq F^{\prime }⊊F$[7].

In other words, the treewidth of a graph $G$ equals the minimum over all triangulations $H$ of $G$ of the maximum clique size of $H$ minus one. The edges added in the construction of a PEO are referred to as fill-in edges.

The design of integer programming formulations was pursued with the goal of surpassing, with contemporary ILP solvers, the performance of state-of-the-art dynamic programming algorithms (Grigoriev’s survey gives historical insights on the first integer programming formulation of the treewidth problem [20]). Unfortunately, even after 20 years, all formulations designed so far are far from being applicable in practice to solve the treewidth problem, mainly due to their inherent symmetry and large integrality gaps [10, 20, 29].

In this paper, we advance this line of research by introducing valid inequalities for the theoretically strongest treewidth formulation currently known, in terms of the quality of its linear relaxation, based on perfect elimination orderings. Since the number of such inequalities is not polynomially bounded, we also develop a separation routine capable of detecting which of them are violated by the canonical linear relaxation solution of the treewidth formulation. Finally, we present an experimental evaluation illustrating the impact of these classes of inequalities on a variety of graphs.

From now on we let $G=(V,E)$ be an unweighted, undirected, simple graph on $n$ vertices and let $\pi :V\to \{1,\mathrm{\dots },n\}$ be a perfect elimination order (PEO) of the vertices of $G$. The graph corresponding to the resulting triangulation given by $\pi$ will be denoted with $H=(V,E\cup F)$ of $G$, where $F$ is the set of fill-in edges. To resolve ambiguity, we will denote with $V(G)$ and $E(G)$ the set of vertices and edges of the graph $G$, respectively. For any subset $W\subseteq V$ of vertices of $G$, we adopt the canonical notation $G[W]$ for the subgraph of $G$ induced by the vertices in $W$. That is, $G[W]$ has $W$ as vertex set and $\{\{u,v\}:u,v\in W,\{u,v\}\in E(G)\}$ as edge set. An induced graph $G[W]$ of $G$ is said to be an induced cycle of length $k$ if $G[W]:=C:=(v_0,v_1,\mathrm{\dots },v_{k-1})$ with $\{v_i,v_{i+1}\}\in E(G)$ for all $i$ (indices taken modulo $k$) and no other edge of $G$ has both endpoints in $\{v_0,\mathrm{\dots },v_{k-1}\}$. Such a subgraph is also known as $k$-hole.

We are now ready to present the first ILP formulation designed for the treewidth problem. As previously described, it is based on Definition 2 linking treewidth to PEOs. In the following, we report the version given by Mallach [29] which he calls ${\text{tw}}_{\text{lo}}$.

Variables $x_{ij}$ and $y_{ij}$ are introduced for every pair of distinct vertices $i,j\in V$. The relation holds if and only if $x_{ij}=1$, and the pair $\{i,j\}$ forms an edge of the triangulation precisely when $y_{ij}=1$ or $y_{ji}=1$. Equations (3) guarantee that each pair of vertices receives an ordering, while the three-di-cycle inequalities (4) enforce the consistency of the ordering $\pi$ encoded by the $x$-variables, namely, transitivity and thus acyclicity of the induced precedence relation, as inherited from the linear ordering polytope [22, 23]. Inequalities (5) impose the required addition of fill-in edges $\{j,k\}\notin E$ to obtain a triangulation. Furthermore, equations (6) ensure that every original edge receives a correctly oriented counterpart in the triangulation, and inequalities (7) enforce that all added edges are oriented consistently with the ordering. Finally, the objective function together with constraints (2) ensures that the variable $w$ correctly represents the treewidth according to Definition 2.

Several other ILP formulations for the treewidth problem have been proposed (see [21, 20, 29]). Among those based on perfect elimination orderings, and their flow metric combination [9, 20], Mallach [29] showed that ${\text{tw}}_{\text{lo}}$ achieves the strongest linear relaxation. We therefore focus on strengthening this formulation.

Recall the role of the decision variables:

• $\mathrm{■}$

  $x_{ij}=1$ if and only if , for all distinct $i,j\in V$;

• $\mathrm{■}$

  $y_{ij}=1$ if and only if $\{i,j\}\in E\cup F$ and , for all distinct $i,j\in V$.

A $0$–$1$ assignment $(x,y)$ is feasible if there exists a chordal supergraph $H=(V,E\cup F)$ of $G$ and a PEO $\pi$ of $H$ such that $x$ and $y$ are induced by $(H,\pi )$ in the sense above. An inequality is valid if it is satisfied by every feasible assignment. In what follows we show that the proposed inequalities are valid in this sense.

Define the set of chord candidates

Given a fractional feasible solution $(\overline{x},\overline{y},\overline{w})$ to the linear relaxation²²2In our case, we relax the domain of each of the $x$ variables to $[0,1]$. of ${\text{tw}}_{\text{lo}}$, we ask whether there exists any of the $k$-holes inequalities (10) which is violated by such solution. In particular, we seek for a $k$-hole $C=(v_0,\mathrm{\dots },v_{k-1})$ in the input graph $G$ for which

where, as above, $𝒞(C)$ denotes the set of nonconsecutive vertex pairs of $C$ that are non-edges of $G$ (i.e., candidate chords).

The task of finding violated inequalities associated with (induced and / or odd) cycles arises in a variety of optimization problems. Classic examples include the stable set polytope [32, 36], the matching polytope [15], and the maximum cut polytope [24, 27] for which odd-hole inequalities have been investigated. As noted earlier, $k$-holes inequalities have also been exploited in the context of the minimum chordal completion polytope. Existing computational studies addressing their separation rely on customized enumeration algorithms for detecting (induced) cycles [4, 3]. However, among all violated inequalities of a given class, one is typically interested in identifying the most violated one, that is, in our setting, the inequality whose left-hand side (LHS) attains the smallest value when evaluated at $\overline{y}$. By assigning to each non-edge $uv\notin E$ of $G$ the weight ${\gamma }_{uv}={\overline{y}}_{uv}+{\overline{y}}_{vu}$, the problem reduces to finding an induced cycle $C$ in $G$ that minimizes the weighted sum of its potential chords. This task can again be formulated as an ILP. In fact, as alternative to algorithms based on complete enumeration, the exact detection of an induced cycle $C$ in $G$ with specific properties (e.g., being the longest one) has recently been investigated by the polyhedral combinatorics community [35, 1]. These formulations usually employ binary variables on the vertices and the edges of the graph, linked by topological constraints inherent to cycles (e.g., the number of selected incident edges to a same vertex is equal to 2, or that the number of selected vertices is equal to the number of selected edges). Then, to prevent the selection of multiple connected components, inequalities such as MTZ constraints or subtour elimination constraints are required [1]. However, these additions tend to introduce a non-negligible computational burden. Indeed, existing formulations can certify optimality only for graphs with fewer than 100 vertices, and often require tens of seconds to do so [35, 1], which is too costly for use within a separation routine.

Since our goal is specifically to detect $k$-holes, we can relax the requirement of identifying only one hole at a time. The ILP formulation presented below is therefore designed to detect induced cycles with $k\ge 4$ that minimize the total chord weight. Being the problem a minimization one, although the formulation may accept more than one induced $k$-hole, the solver will select two or more in the case where all of them have weighted chord sum equal to $0$. Otherwise, removing any additional hole would yield a solution with a strictly smaller objective value.

The model is inspired by the formulation CCP (Chordless Cycle Problem) [35]. Introduce binary variables

• $\mathrm{■}$

  $z_v\in \{0,1\}$ for each $v\in V$, which indicates whether vertex $v$ is selected in the cycle;

• $\mathrm{■}$

  $c_{uv}\in \{0,1\}$ for each $\{u,v\}\in E$, that indicates whether edge $\{u,v\}$ is used as a cycle edge.

• $\mathrm{■}$

  $q_{uv}\in \{0,1\}$ for each $\{u,v\}\notin E$ indicates that both endpoints $u$ and $v$ are selected in the cycle; it is used to accumulate the chord weights ${\gamma }_{uv}$ in the objective.

The separation ILP, called sep, reads:

The objective (12) minimizes the total fractional chord weight over all non-edges whose endpoints lie on the chosen cycle. A violated $k$-hole inequality is obtained whenever the optimal value is strictly smaller than $k-3$ for the corresponding cycle length $k$. Constraint (13) enforces that each selected vertex has degree 2 in the chosen edges, so the selected edges form a $2$-regular subgraph. Constraints (19) avoid the selection of 3-holes, namely triangles, where $𝒯$ is the set of triangles in the graph. Constraint (14) states that if both endpoints of an edge $\{u,v\}\in E$ are selected ($z_u=z_v=1$), then the edge must be used in the cycle ($c_{uv}=1$). This, together with constraint (13), forbids chords among the selected vertices, so the resulting cycle is induced. Constraints (15)–(17) implement the logical relation $q_{uv}=z_u\wedge z_v$ for each non-edge $\{u,v\}\notin E$. Thus $q_{uv}=1$ exactly when both endpoints of a potential chord are on the cycle, allowing the objective to sum the corresponding weights ${\gamma }_{uv}$. Constraint (18) requires the selection of at least $k_{\min }$ vertices (e.g., $k_{\min }=4$). Constraints (20)–(22) specify the binary nature of the decision variables.

To the best of our knowledge, this work provides the first separation of most-violated $k$-hole inequalities in the context of triangulation-related problems.

We experimentally evaluate ${\text{tw}}_{\text{lo}}^{\text{sep}}$ with respect to the following research question: Will ${\text{tw}}_{\text{lo}}^{\text{sep}}$ yield better lower bounds than ${\text{tw}}_{\text{lo}}$ on both synthetic and real-world graph topologies? This is a common approach in polyhedral combinatorics to evaluate the quality of valid inequalities (see, e.g., the work of Jünger and Mallach on the maximum cut polytope [27]).

We have introduced a family of valid inequalities for the strongest currently known integer programming formulation ${\text{tw}}_{\text{lo}}$ of treewidth based on perfect elimination orderings. These inequalities, derived from the structure of induced cycles, strengthen the canonical linear relaxation by enforcing constraints that every feasible chordal completion must satisfy. Because the number of such inequalities is not polynomially bounded, we developed a separation routine capable of identifying violated $k$-hole inequalities efficiently within a cutting-plane framework.

Our computational results demonstrate the practical impact of these inequalities. Across all tested graph classes, the plain relaxation of ${\text{tw}}_{\text{lo}}$ provides weak lower bounds, often far from the true treewidth. Incorporating the violated $k$-hole inequalities through the cutting plane routine ${\text{tw}}_{\text{lo}}^{\text{sep}}$ substantially improves these bounds. These results confirm that the proposed inequalities capture important structural information that the base formulation fails to enforce.

Several research questions remain open. In particular, exploring alternative strategies for detecting chordless cycles, such as approaches based on decomposing induced simple cycles [27], may lead to more scalable separation routines. Moreover, developing techniques to break the symmetries inherent in PEO-based treewidth formulations still remains an open problem, and progress on it could substantially improve the effectiveness of ILP approaches for computing the exact treewidth of graphs. Finally, an interesting direction for further study is to assess the potential of $k$-holes separation routines based on induced-cycle ILP formulations, such as sep, when applied to the minimum chordal completion polytope [3].