# New lower bounds on the cutwidth of graphs

Jean-Claude Bermond, Michel Cosnard, David Coudert, Frédéric Havet

► To cite this version:

Jean-Claude Bermond, Michel Cosnard, David Coudert, Frédéric Havet. New lower bounds on the cutwidth of graphs. Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France. 2024. [hal-04774458](https://hal.science/hal-04774458v1)

HAL Id: hal-04774458

https://hal.science/hal-04774458v1

Submitted on 8 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# New lower bounds on the cutwidth of graphs*

Jean-Claude Bermond and Michel Cosnard and David Coudert and Frédéric Havet

Université Côte d'Azur, Inria, CNRS, I3S, France

November 8, 2024

## Abstract

Cutwidth is a parameter used in many layout problems. Determining the cutwidth of a graph is an NP-complete problem, but it is possible to design efficient branch-and-bound algorithms if good lower bounds are available for cutting branches during exploration. Knowing how to quickly evaluate good bounds in each node of the search tree is therefore crucial.

In this article, we give new lower bounds based on different graph density parameters. In particular, we give bounds using the notion of traffic grooming on a path network, which appear to be in many cases better than bounds in the literature. Furthermore, the bounds based on grooming can be computed quickly and so are of interest to design faster branch-and-bound algorithms.

**Keywords:** Cutwidth; lower bounds; traffic grooming; density

## 1 Introduction

Graph layout problems are a particular class of combinatorial optimization problems whose goal is to find a layout of an input graph in such a way that a certain objective cost is optimized. A *layout* of a graph $G = (V, E)$ is a linear ordering $\sigma = (v_1, \dots, v_n)$ of the vertices of $G$. A large amount of relevant problems in different areas can be formulated as graph layout problems (see the survey [19] and references therein).

The *edge-cut* of a set $X \subseteq V$ is the set of edges with one end-vertex in $X$ and the other in $\bar{X} = V \setminus X$. Its size is denoted by $\text{ec}(X, \bar{X})$. Let $X_i = \{v_1, \dots, v_i\}$. The *width* $w(G, \sigma)$ of a graph $G$ with respect to the layout $\sigma$ is the maximum of $\text{ec}(X_i, \bar{X}_i)$ over all $i \in \{1, \dots, n-1\}$. The *cutwidth* of a graph $G$, denoted by $\text{cw}(G)$, is the minimum width of a layout, that is $\text{cw}(G) = \min\{w(G, \sigma) \mid \sigma \text{ layout of } G\}$.

The cutwidth was first used as a theoretical model for the number of channels in an optimal layout of a circuit in the seventies [3,21]. In general, the cutwidth of a graph times the order of the graph gives a measure of the area needed to represent the graph in a VLSI layout when vertices are laid out in a row [20]. More recent applications of this problem include network reliability [18], automatic graph drawing [22], information retrieval [5] and as a subroutine for the cutting plane algorithm to solve the traveling salesman problem [17]. Due to its natural definition, the cutwidth has various applications in computer science: whenever data is expected to be roughly linearly ordered and dependencies or connections are local, the cutwidth of the

<footnote>*This work has been supported by the French government, through the UCA<sup>JEDI</sup> Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-15-IDEX-01. A preliminary version of this paper appears in [8].</footnote>
20

corresponding graph is expected to be small. However, computing the cutwidth of graphs is NP-hard [19] in general. Exact exponential-time algorithms using dynamic programming have been proposed in [10], one with time and space complexity in $O^*(2^n)$, and another with time complexity in $O^*(4^n)$ and polynomial space complexity (the $O^*$ notation hides factors that are polynomial in $n$). Fixed-parameter algorithms have also been designed [26, 41] and a $O(\log^{1+o(1)} n)$ approximation algorithm has been proposed in [4]. Furthermore efficient branch-and-bound algorithms have been proposed [35] but they need to have good lower bounds for the cutwidth, and in particular bounds that can be quickly evaluated at each node of the branch-and-bound tree. The quality of these bounds have a strong impact on the performances of the branch-and-bound algorithms. Finally, let us mention the recently proposed methods for computing lower bounds on the cutwidth of a graph based on semidefinite programming (SDP) relaxation [24], which are able to produce good lower bounds but at a high computational cost.

25

Interestingly, for any graph of order $n \le 31$, an optimal solution for cutwidth can be obtained within seconds using the implementation available in SageMath [40] of the dynamic programming algorithm proposed in [10] with time and space complexity in $O^*(2^n)$. For larger graphs, one can use for instance integer linear programming formulations [16], the branch-and-bound algorithm proposed in [35] or the methods based on semidefinite programming proposed in [24]. However, these methods usually require hours of computations for graphs with 50 vertices.

30

35

**Our results.** In this paper, we first review previous lower bounds on the cutwidth of a graph (Section 2). Next, we introduce new lower bounds based on the maximum, minimum or maximum average degree of $G$ (Section 3). Note that all these parameters can be computed in polynomial time. Moreover, the bounds are mostly incomparable and hence are complementary. We then present in Section 4 a new lower bound based on the results obtained for the *Maximum All request Path Grooming problem* [9], a problem also known as the *Call Control Problem in Path Networks* in [2]. This new bound indicates the minimum cutwidth of any graph with $n$ vertices and $m$ edges, independently from the structure of the graph, and it can be computed in time $O(\log n)$. Furthermore, we prove that this new bound is better than bounds based on the average degree of the graph. Finally, we report in Section 5 experimental comparisons of these bounds on various graph classes. In particular, we exhibit different behaviors on Erdős-Rényi random graphs and on random (proper) interval graphs.

40

45

50

**Notations.** All the graphs considered in this paper are finite, undirected, unweighted and simple (without loops nor multiple edges). The graph $G = (V, E)$ has $n = |V|$ vertices and $m = |E|$ edges. Let $N(v)$ denotes the set of neighbors of $v \in V$, that is $N(v) = \{u | uv \in E\}$. Let $d(v) = |N(v)|$ denotes the degree of vertex $v \in V$, and let $\delta(G)$ and $\Delta(G)$ denote respectively the minimum and maximum degree of $G$.

55

We will use the following property of cutwidth.

**Property 1.** For any subgraph $H$ of a graph $G$, we have $cw(G) \ge cw(H)$.

## 2 Previous lower bounds

In this section, we survey the lower bounds on the cutwidth of graphs that have previously been proposed [19, 31, 33, 35].

**Bound based on minimal edge-cuts.** From the definition of cutwidth, it is obvious that the minimum size of an edge-cut between any pair $u, v$ of vertices of the graph, which we denote
by $\kappa'(u, v)$, is a lower bound on its cutwidth (see [19] for more details). So, we get:

$$ \mathrm{cw}(G) \geq \mathrm{LB}_{\kappa'}(G) = \max\{\kappa'(u, v) \mid u, v \in V, u \neq v\} \quad (1) $$

This bound can be computed in $O(m^{1+o(1)})$ time using the ground-breaking algorithm proposed in [1] for building the Gomory-Hu tree [28] of the graph, which uses the algorithm proposed in [14] for computing a maximum flow in $O(m^{1+o(1)})$ time.

**Bound based on the algebraic connectivity.** Let $\lambda_2$ denote the second smallest eigenvalue of the Laplacian matrix associated with the graph. The following lower bound is due to [31]:

$$ \mathrm{cw}(G) \geq \mathrm{LB}_{\lambda_2}(G) = \frac{\lambda_2}{n} \lfloor \frac{n}{2} \rfloor \lfloor \frac{n}{2} \rfloor \quad (2) $$

The time complexity of this bound is due to the computation of $\lambda_2$, which requires $O(n^\omega)$ time [39], with $\omega \le 2.371552$ [43], but fast numerical methods can be used to compute eigenvalues in practice [34].

Note that $\lambda_2$ is known as the algebraic connectivity of a graph. It reflects how well the overall graph is connected (the larger the better). For instance, for the complete graph $K_n$, we have $\lambda_2(K_n) = n$, while for the hypercube $Q_n$ of dimension $n \ge 2$, we have $\lambda_2(Q_n) = 2$. The algebraic connectivity of any non-clique graph $G$ is upper bounded by its vertex-connectivity $\nu(G)$ and its edge-connectivity $\kappa(G)$, i.e., $\lambda_2 \le \nu(G) \le \kappa(G)$ [23]. Furthermore, it is lower bounded by $\frac{1}{n \mathrm{diam}(G)}$ [37], where $\mathrm{diam}(G)$ denotes the diameter of the graph. Hence, it is equal to 0 if the graph is not connected and is larger than 0 otherwise.

**Bound based on the maximum degree.** Let $\Delta(G)$ denote the maximum degree of $G$, let $v_i$ be a vertex with degree $\Delta(G)$ and consider a layout $(v_1, \dots, v_n)$ of $G$. One set among $\{v_1, \dots, v_{i-1}\}$ and $\{v_{i+1}, \dots, v_n\}$ contains at least half of the neighbours of $v_i$. Consequently,

$$ \mathrm{cw}(G) \geq \mathrm{LB}_{\Delta}(G) = \left\lfloor \frac{\Delta(G)}{2} \right\rfloor \quad (3) $$

Depending on the data structure used for storing the graph, this bound can be computed for instance in $O(n)$ time when the degree of a vertex can be accessed in constant time, or in $O(n+m)$ time when it is necessary to scan all the edges to first determine the degrees of the vertices.

**Bound based on the degeneracy.** A graph $G$ is $k$-degenerate if every subgraph $H$ of $G$ has minimum degree at most $k$. Equivalently, $G$ is $k$-degenerate, if there exists a layout $(v_1, \dots, v_n)$ such that for all $i \in \{2, \dots, n\}$ every vertex $v_i$ has at most $k$ neighbours in $\{v_1, \dots, v_{i-1}\}$. The degeneracy of $G$, denoted by $\delta^*(G)$, is the smallest $k$ such that $G$ is $k$-degenerate.

The following lower bound is proved in [33].

$$ \mathrm{cw}(G) \geq \mathrm{LB}_{\delta^*}(G) = \frac{1}{4} \delta^*(G) (\delta^*(G) + 2) \quad (4) $$

The degeneracy of a graph can be computed in $O(n+m)$ time [36] and so does this bound.

Other lower bounds can be obtained using linear programming [4] and SDP relaxation [24]. However, they cannot be computed in a reasonable time for graphs with more than 50 vertices.
## 3 New lower bound based on degrees

In this section, we propose new lower bounds on the cutwidth of a graph based on the minimum and the average degree.

**Bound based on the minimum degree.** Let $\delta(G)$ denote the minimum degree of $G$. Let $\sigma = (v_1, \dots, v_n)$ be a layout of $G$. Set $k = \lfloor \delta(G)/2 \rfloor + 1$ and let $X_k = \{v_1, \dots, v_k\}$. Every vertex in $X_k$ has at most $k-1 = \lfloor \delta(G)/2 \rfloor$ neighbours in $X_k$ and so at least $\lfloor \delta(G)/2 \rfloor$ neighbours in $\overline{X_k}$. Hence $\mathrm{ec}(X_k, \overline{X_k}) \ge k \lfloor \delta(G)/2 \rfloor = (\lfloor \delta(G)/2 \rfloor + 1) \lfloor \delta(G)/2 \rfloor$. Thus

$$ \mathrm{cw}(G) \ge \mathrm{LB}_{\delta}(G) = (\lfloor \delta(G)/2 \rfloor + 1) \lceil \delta(G)/2 \rceil \ge \frac{1}{4} \delta(G)(\delta(G) + 2) \quad (5) $$

As $\delta^*(G) \ge \delta(G)$, the bound of Ineq. (4) is better than the bound of Ineq. (5). However by definition of degeneracy, there is a subgraph $H$ of $G$ such that $\delta(H) = \delta^*(G)$. Since $\mathrm{cw}(G) \ge \mathrm{cw}(H)$, Ineq. (5) implies the bound of Ineq. (4) (with a simpler proof than the original one [33]).

The time complexity for computing the bound based on the minimum degree is the same as for the bound based on the maximum degree.

**Bound based on the average degree.** Let $\sigma = (v_1, \dots, v_n)$ be a layout of $G$ and let $X_i = \{v_1, \dots, v_i\}$. For each vertex $v_i$, let $d^+(v_i)$ be the number of edges $v_i v_j \in E(G)$ with $j > i$ (forward edges from $v_i$).

**Proposition 1.** $w(G, \sigma) \ge \frac{1}{2(n-1)} \sum_{i=1}^{n-1} d^+(v_i)(d^+(v_i) + 1)$

*Proof.* We use a classical trick in (traffic) grooming. We first compute the total load of $G$ on $P_\sigma = v_1 v_2 \dots v_n$, also called sum cut of the layout $\sigma$ [19], which is $L(G, \sigma) = \sum_{i=1}^{n-1} l(v_i v_{i+1}) = \sum_{i=1}^{n-1} \mathrm{ec}(X_i, \overline{X_i})$, where $l(v_i v_{i+1})$ denotes the “load” of the edge $v_i v_{i+1}$ of $P_\sigma$, that is the number of edges $v_j v_\ell \in E(G)$ such that $j \le i < \ell$. To compute $L(G, \sigma)$, we note that the load of the forward edges of $G$ from $v_i$ is at least $d^+(v_i)$ on the edge $v_i v_{i+1}$, at least $d^+(v_i) - 1$ on the edge $v_{i+1} v_{i+2}$ and so on. Therefore the load due to the edges from $v_i$ is at least $\frac{1}{2} d^+(v_i)(d^+(v_i) + 1)$ and the total load is at least $\frac{1}{2} \sum_{i=1}^{n-1} d^+(v_i)(d^+(v_i) + 1)$. Then we note that, as the path has $n-1$ edges, there exists an edge with load at least $\frac{L(G, \sigma)}{n-1}$ and so $w(G, \sigma) \ge \frac{L(G, \sigma)}{n-1}$. $\square$

The *average degree* of a graph $G$ with $m$ edges and $n$ vertices is $\mathrm{Ad}(G) = 2m/n$.

If a function $f(x)$ is convex and if $\sum_{i=1}^{n-1} x_i = m$, then the minimum of $\sum_{i=1}^{n-1} f(x_i)$ is attained when all the $x_i$ are equal to $m/(n-1)$. Applying this argument to the convex function $x \mapsto x(x+1)$ with $x_i = d^+(v_i)$ and using the fact that $\sum_{i=1}^{n-1} d^+(v_i) = m$, we get:

$$ \mathrm{cw}(G) \ge \mathrm{LB}_{\mathrm{Ad}}(G) = \frac{1}{2} \frac{m}{n-1} \left( \frac{m}{n-1} + 1 \right) = \frac{1}{8} \left( 1 + \frac{1}{n-1} \right)^2 \mathrm{Ad}(G) \left( \mathrm{Ad}(G) + 2 - \frac{2}{n} \right) \quad (6) $$

Clearly, this bound can be computed in $O(1)$ time.

The bounds given by Ineq. (4) and (6) are incomparable. Indeed, on the one hand, there exist graphs with bounded average degree and degeneracy as large as we want. For example, consider the graph $H_k^i$ obtained by identifying one vertex of the clique $K_k$ of order $k$ with an extremity of the path $P_i$ of order $i$. Then the degeneracy is $k-1$ but the average degree tends to 2 when $i$ tends to infinity. So for $i$ large, the bound of Ineq. (4) is better. In Table 1, we have given the value of the lower bounds for $k=50$.
On the other hand, consider the graph $G(s, n)$ with $n$ vertices where vertex $v_i$ is joined to the $s$ vertices $v_{i+h}$, with $1 \le h \le s$ and $i+h \le n$. Then its degeneracy is $s$ (consider the layout $(v_1, \dots, v_n)$), but we have $m = sn - s(s+1)/2$ and so for $n$ large the bound of Ineq. (6) is better. In Table 2, we have given the value of the lower bounds for $n = 2s+1$.

**Bound based on the maximum average degree.** The maximum average degree of $G$ is $\text{Mad}(G) = \max\{\text{Ad}(H) \mid H \text{ subgraph of } G\}$. Observe that this parameter can be computed in polynomial time [11, 12, 15, 25, 27, 32]. By definition of Mad, there is at least one subgraph $H$ of $G$ such that $\text{Ad}(H) = \text{Mad}(G)$. Since $\text{cw}(G) \ge \text{cw}(H)$, Ineq. (6) directly implies

$$ \text{cw}(G) \ge \text{LB}_{\text{Mad}}(G) = \max \{ \text{LB}_{\text{Ad}}(H) \mid H \text{ subgraph of } G \text{ such that } \text{Ad}(H) = \text{Mad}(G) \} \quad (7) $$

Let $n_{H_0}$ be the number of vertices of the smallest subgraph $H_0$ such that $\text{Ad}(H_0) = \text{Mad}(G)$, and let $m_{H_0}$ be its number of edges. This subgraph maximizes $m_{H_0}/(n_{H_0} - 1)$ among all the subgraphs of $G$ with average degree $\text{Mad}(G)$. Then, from Ineq. (6) and 7, we get

$$ \text{cw}(G) \ge \text{LB}_{\text{Mad}}(G) = \frac{1}{2} \frac{m_{H_0}}{n_{H_0} - 1} \left( \frac{m_{H_0}}{n_{H_0} - 1} + 1 \right) \quad (8) $$

The following tight inequalities are well-known (see e.g. Proposition 3.1 of [38]): $\delta^*(G) \le \text{Mad}(G) < 2\delta^*(G)$. Thus the bounds given by Ineq. (4) and (8) are incomparable. The lower bound of Ineq. (8) is better than the bound of Ineq. (4) when $\text{Mad}(G) > \sqrt{2\delta^*(G)}$ and worse in the other case.

It has been shown in [25, 27] that $\text{Mad}$ can be determined in $O(nm \log(n^2/m))$ time using a maximum-flow computation. Furthermore, efficient approximation algorithms have been proposed, such as a $(1-\epsilon)$-approximation algorithm with time complexity in $\tilde{O}(m/\epsilon)$ [11, 13] (the $\tilde{O}$ notation hides logarithmic factors in $n$).

# 4 A lower bound using the grooming on the path

In this section, we present a new lower bound on the cutwidth of a graph based on the results obtained for the Maximum All request Path Grooming problem [9], a problem also known as the Call Control Problem in Path Networks in [2].

Consider the path $P_\sigma = v_1v_2\cdots v_n$ associated to the layout $\sigma = (v_1, v_2, \cdots, v_n)$. For each edge $e \in E(G)$, the request associated to $e$ by $\sigma$, denoted by $R_\sigma(e)$, is the subpath of $P_\sigma$ whose end-vertices are those of $e$. Let $\mathcal{R}_\sigma(G)$ be the set of requests associated by $\sigma$ to the edges of $G$. Observe that the load of the edge $v_iv_{i+1}$ in $P_\sigma$ under $\mathcal{R}_\sigma(G)$ denoted $l(v_iv_{i+1})$ is the number of edges $v_jv_\ell$ of $G$ with $j \le i < \ell$, that is $\text{ec}(X_i, \bar{X}_i)$. Hence $w(G, \sigma)$ is the maximum load of an edge of $P_\sigma$ under $\mathcal{R}_\sigma(G)$.

The grooming factor $C$ is the maximum load that is allowed on the edges of $P$. Given a grooming factor $C$, the maximum number of requests that can be satisfied (or groomed) together on $P$ such that the load of any edge is at most $C$ is denoted by $T(C, n)$.

We note that the value $T(C, n)$ is nothing else than the maximum number of edges of a simple graph of order $n$ with cutwidth $C$ and we emphasize this observation as a proposition.

**Proposition 2.** Let $n$ and $C$ be positive integers. The maximum number $m$ of edges of any simple graph $G$ of order $n$ and cutwidth $\text{cw}(G) \le C$ is $m = T(C, n)$.

It follows that for a given value $C$, any graph of order $n$ with $m = T(C, n)$ edges has cutwidth at least $C$. Let $\sigma$ be a layout of $G$ such that $w(G, \sigma) = \text{cw}(G)$. As $w(G, \sigma)$ is the maximum
load of an edge of $P_\sigma$ under $\mathcal{R}_\sigma(G)$, we have $T(\mathrm{cw}(G), n) \ge m$, and so

$$ \mathrm{cw}(G) \ge C^*(m, n) = \min \{C \mid m \le T(C, n)\} \qquad (9) $$

Note that the bound is reached by taking as edges of $G$ the pairs of end-vertices of the $T(C^*(m, n), n)$ requests that can be groomed on a path of $n$ vertices with grooming factor $C^*(m, n)$. This set of requests can be found in polynomial time using the greedy algorithm proposed in [9]. In other words, one can find in polynomial time a graph with $n$ vertices, $m = T(C^*(m, n), n)$ edges and cutwidth $\mathrm{cw}(G) = C^*(m, n)$.

We will see later (Proposition 4) that we can efficiently compute the value of $C^*(m, n)$ thanks to the results of [9] where a closed formula for $T(C, n)$ has been given.

First, we note that if $C \ge \lfloor n^2/4 \rfloor$, then we can satisfy all requests and so $T(C, n) = n(n-1)/2$. If $C = 1$, the determination of $T(1, n)$ is easy as an optimal solution consists in taking the $n-1$ requests of length 1 (that are the requests $(i, i+1)$ for $1 \le i \le n-1$) and so $T(1, n) = n-1$. In [7] it is also proven that for $C = 2$, we have $T(2, n) = \lfloor (3n-3)/2 \rfloor$. The optimum can be easily found for $C \le 6$; in particular for $C = 3$ (respectively, $C = 6$ and $n \ge 6$) the maximum is obtained by considering all requests of length 1 and 2 (resp. 1, 2 and 3).

Based on these results, it was conjectured the “intuitive fact” that the optimum was obtained by taking the greedy solution consisting of all requests of smallest length (this was presented as a result in [19]). However, this is true only for $C \le 9$ and it appears that the conjecture is false. In particular, one could have expected that, for $C = C_s = s(s+1)/2$, an optimal solution would be obtained by taking all requests of length at most $s$ in number $sn - C_s$ (the graph of requests being the graph $G(s, n)$ used in Section 3 to show that the bound of Ineq. (6) is better than that of Ineq. (4). But it is not true for $n = 11$ and $C = 10$ ($s = 4$). The solution with all requests of length at most 4 has $4 \times 11 - 10 = 34$ requests. The maximum load is 10, but it is reached only for the edges of the path $v_1 \cdots v_{11}$ of the form $v_iv_{i+1}$ with $4 \le i \le 8$. So we can delete the request of length 4 $v_4v_8$ and add the two requests of length 5 $v_1v_6$ and $v_6v_{11}$ to get a solution with 35 requests. We summarize the results of [9] giving the value of $T(C, n)$:

**Theorem 1 ([9]).** Let $n$ and $C$ be fixed positive integers.

* If $C \ge \lfloor \frac{n^2}{4} \rfloor$, then $T(C, n) = \frac{n(n-1)}{2}$;

* If $n$ is even and $\frac{n(n-2)}{8} < C \le \lfloor \frac{n^2}{4} \rfloor$, then $T(C, n) = \frac{n(n-2)}{4} + C$;

* If $n$ is odd and $\frac{n^2-1}{8} < C \le \lfloor \frac{n^2}{4} \rfloor$, then $T(C, n) = \frac{(n-1)^2}{4} + C$.

* Otherwise, let $s$ be an integer such that $C_{s-1} < C \le C_s$ with $C_s = \frac{s(s+1)}{2}$; $d = C_s - C$; $n = qs+r$ with $0 \le r < s$; $r = aq+\alpha$ with $0 \le \alpha < q$; $s-r = b(q+1)+\beta$ with $0 \le \beta \le q$; $A(C, n) = ar - \frac{a(a+1)}{2}q$ and $B(C, n) = (b+1)(s-r) - \frac{b(b+1)}{2}(q+1)$. We have

$$ T(C, n) = sn - C_s - dq + \min \{A(C, n) + d, B(C, n)\} $$

We will now show (Proposition 3) that the bound of Ineq. (9) is better than that of Ineq. (6). For that we use the upper bound on $T(C, n)$ given in [9].

**Theorem 2 (Theorem 17 in [9]).** Let $n$ and $C$ be fixed positive integers. Let $s$ be an integer such that $C_{s-1} < C \le C_s$ with $C_s = \frac{s(s+1)}{2}$, let $d = C_s - C$ and let $n = qs + r$ with $0 \le r < s$. We have

$$ T(C, n) \le sn - C_s - dq + (5 - 2\sqrt{6})C + \min\{d, s-r\} $$
**Proposition 3.** Let $n \ge 2$ and $m \ge 0$ be positive integers. We have $C^*(m, n) \ge \text{LB}_{\text{Ad}}(m, n)$.

*Proof.* If $m \le n - 1$, the proposition is obviously true. In fact, we have $\text{LB}_{\text{Ad}}(m, n) \le 1$ while $C^*(1, n) = C^*(2, n) = \dots = C^*(n-1, n) = 1$ and $\text{LB}_{\text{Ad}}(0, n) = 0 = C^*(0, n)$. So in what follows we suppose $m > n - 1$

175

We first consider the case when $m/(n-1)$ is an integer $s \ge 2$. Then, we have $\text{LB}_{\text{Ad}}(m, n) = \frac{1}{2} \frac{m}{n-1} \left( \frac{m}{n-1} + 1 \right) = s(s+1)/2$. According to the definition of $C^*(m, n)$, it suffices to prove that, for $C_b = \text{LB}_{\text{Ad}}(m, n) = s(s+1)/2 = C_s$ we have $T(C_s, n) \le m$.

180

By Theorem 2, we get, as $d=0$, that $T(C_s, n) \le sn - C_s + (5 - 2\sqrt{6})C_s = sn - (2\sqrt{6} - 4)C_s$. As $m = sn - s$ and $(2\sqrt{6} - 4)C_s > s$ for $s \ge 2$, we conclude that $T(C_s, n) < m$ and so $C^*(m, n) > C_s$.

185

Otherwise, let $s = \lfloor m/(n-1) \rfloor$, and so $m = (s-\tau)(n-1)$ with $0 \le \tau < 1$. Let $C_s = s(s+1)/2$ and $C_b = \text{LB}_{\text{Ad}}(m, n) = \frac{1}{2}(s-\tau)(s+1-\tau) = C_s - \tau s - \tau/2 + \tau^2/2$. In general $C_b$ is not an integer. Consider the function $f(C_b, n) = sn - C_s - dq + (5 - 2\sqrt{6})C_b + \min\{d, s-r\}$ where $d = C_s - C_b = \tau s + \tau/2(1 - \tau/2)$. We have $T(\lfloor C_b \rfloor, n) \le f(C_b, n)$ and so according to the definition of $C^*(m, n)$, the proposition is true if $T(\lfloor C_b \rfloor, n) < m$. Therefore, it suffices to prove that $f(C_b, n) < m$.

We note that, $d \ge \tau s$ as $0 \le \tau < 1$; $\min\{d, s-r\} \le d$ and $C_b \le C_s$. Therefore, it suffices to verify that $sn - (2\sqrt{6} - 4)C_s - \tau s(q-1) \le m$. Using $m = (s-\tau)(n-1)$, that corresponds to verify that $(2\sqrt{6} - 4)C_s + \tau s(q-1) \ge s + \tau(n-1)$, or, as $n = qs + r \le qs + s - 1$, that $(2\sqrt{6} - 4)C_s - \tau s \ge s + \tau(s-2)$, or equivalently that

$$ (\sqrt{6}-2)(s+1) \ge 1+2\tau-2\tau/s $$

For $s \ge 6$, the inequality is true as $7(\sqrt{6}-2) \ge 3 > 1 + 2\tau$.

For $s = 5$, it is true as $6(\sqrt{6}-2) \ge 13/5 \ge 1 + 8\tau/5$.

190

For $s = 4$, it is true if $5(\sqrt{6}-2) \ge 1 + 3\tau/2$, which is the case if $\tau \le (10\sqrt{6}-22)/3 \approx 0.81$. If $s = 4$ and $\tau \ge (10\sqrt{6}-22)/3$ then $3 < m/(n-1) \le (34 - 10\sqrt{6})/3$ and so $\text{LB}_{\text{Ad}}(m, n) < 7$. On the other side, for $C = 6$ we have $T(6, n) = 3n-6 < m$ and so $C^*(m, n) \ge 7$, proving the proposition.

For $s = 3$, it is true if $4(\sqrt{6}-2) \ge 1 + 4\tau/3$, which is the case if $\tau \le (12\sqrt{6}-27)/4 \approx 0.6$. If $s = 3$ and $\tau \ge (12\sqrt{6}-27)/4$, then $2 < m/(n-1) \le (39 - 12\sqrt{6})/4$ and so $\text{LB}_{\text{Ad}}(m, n) < 5$. On the other side, for $C = 4$ we have $T(4, n) = \lfloor(7n-10)/3\rfloor$. Then, either $m > T(4, n)$ and so $C^*(m, n) \ge 5$ and in this case the proposition is true. Otherwise, $m \le T(4, n) < 7(n-1)/3$ and so $\text{LB}_{\text{Ad}}(m, n) < 70/18 < 4$ while $T(3, n) = 2n-3 < m$, and so $C^*(m, n) \ge 4$, and therefore the proposition is also true in this case.

195

For $s = 2$, it is true if $3(\sqrt{6}-2) \ge 1 + \tau$ which is the case if $\tau \le 3\sqrt{6} - 7 \approx 0.35$. If $s = 2$ then $1 < m/(n-1) < 2$ and so $\text{LB}_{\text{Ad}}(m, n) < 3$. For $C = 2$, $T(2, n) = \lfloor(3n-3)/2\rfloor$. Then either $m > T(2, n)$ and so $C^*(m, n) \ge 3$ and in this case the proposition is true. Otherwise $m \le T(2, n) < 3(n-1)/2$ and so $\text{LB}_{\text{Ad}}(m, n) < 15/8 < 2$ while $T(1, n) = n-1 < m$ and so $C^*(m, n) \ge 2$ and therefore the proposition is also true in this case. $\square$

200

205

The gap between the bounds can be significant. According to Theorem 1, for $C = C_s$ and $n = 2s + 1$, we have $T(C, n) = sn - C_s$; indeed $d = 0$ and $A(C, n) = 0$ as $a = 0$. For example, for $s = 5$ and $n = 11$, we have $T(15, 11) = 40$; but Ineq. (6) gives $\text{LB}_{\text{Ad}}(40, 11) = 10 < 15$. More generally, for $C = C_s$ and $n = 2s + 1$ we get $T(C, n) = sn - C_s = (3s^2 + s)/2$ and $\text{LB}_{\text{Ad}}(m, n) = \text{LB}_{\text{Ad}}((3s^2 + s)/2, 2s + 1) = (9s^2 + 18s + 5)/32$, and so the ratio $C_s/\text{LB}_{\text{Ad}}(m, n)$ tends to $16/9$ when $s$ increases. See also the examples reported in Table 2.

210

In summary, the bounds given in this section are better than the bounds based on degrees. Furthermore, since the value of $T(C, n)$ can be computed in time $O(1)$, the bound of Ineq. (9) can be computed efficiently.
**Proposition 4.** Given two integers $n$ and $m$, the bound $C^*(m, n)$ can be computed in $O(\log n)$ time.

*Proof.* Obviously, when $n < 2$ or $m = 0$, then the bound is 0, and when $1 \le m \le n - 1$, it is 1. When $m = n(n - 1)/2$, then by Theorem 1, $C^*(m, n) = \lfloor n^2/4 \rfloor$. It remains to consider the case in which $n - 1 < m < n(n - 1)/2$. Since the function $C^*$ increases with $m$ (i.e., $C^*(m + 1, n) \ge C^*(m, n)$), we can find $C^*(m, n)$ using binary search on the interval $[C_1 = 1, C_2 = \lfloor n^2/4 \rfloor]$. Indeed, we can compute $T(C_p, n)$, with $C_p = \lfloor (C_l + C_2)/2 \rfloor$, and compare this value to $m$ to decide which subinterval to consider next and so on. The number of iterations of the binary search is in $O(\log n)$ and each computation of $T(C_p, n)$ requires $O(1)$ time. This concludes the proof.

Note that we can start the search with a shorter interval. Indeed, by Theorem 2 when $C = C_s$ we have $sn - C_s \le T(C_s, n) \le sn - C_s + (5 - 2\sqrt{6})C_s$. So, if we let $s_1$ be the real number such that $m = s_1n - s_1(s_1 + 1)/2$, we have $C^*(m, n) \le C_{\lfloor s_1 \rfloor}$. If $s_2$ is such that $m = s_2n - (2\sqrt{6} - 4)s_2(s_2 + 1)/2$, we have $C^*(m, n) \ge C_{\lfloor s_2 \rfloor}$. It follows that we can start the binary search with the interval $[C_{\lfloor s_2 \rfloor}, C_{\lfloor s_1 \rfloor}]$. $\square$

Lower bounds in branch-and-bound algorithms can be quickly computed by using $C^*(m, n)$ (or a good approximation) or the bounds of Ineq. (6) or Ineq. (5). We can also use the better bound of Ineq. (8) but it needs the computation of $\text{Mad}(G)$ which is polynomial but long in practice. We can also use an improvement of Ineq. (9) by noting that $\text{cw}(G) \ge \text{cw}(H)$ for any subgraph $H$ of $G$. So, if we consider like for Ineq. (8) the subgraph $H_0$ with the minimum number $n_{H_0}$ of vertices such that $\text{Ad}(H_0) = \text{Mad}(G)$, and let $m_{H_0}$ be its number of edges:

$$ \text{cw}(G) \ge C_{\text{Mad}}^*(G) = C^*(m_{H_0}, n_{H_0}) \qquad (10) $$

The design of a fast algorithm for computing the bounds of Ineq. (10) seems, however more challenging and we let it as an interesting open problem. However, one can use existing exact and approximate algorithms for finding dense subgraphs to get a good lower bound (see, e.g., [11, 12, 42]). For instance, we can use the method proposed in [12] for finding an approximation of the maximum average degree of a graph (see the bounds $C_g^*$ and $C_{g++}^*$ defined in Section 5.1).

# 5 Experimental evaluation

In this section, we compare the different lower bounds presented in this paper on synthetic graphs (Section 5.2), Erdős-Rényi random graphs (Section 5.3) and random (proper) interval graphs (Section 5.4). We also compare these lower bounds with the values obtained in [24] using SDP relaxation on some random graphs (Section 5.5). We start by presenting our experimental settings in Section 5.1.

## 5.1 Experimental settings

We have implemented all the bounds mentioned in this paper using SageMath [40], Cython [6], SciPy [44] (for computing the eigenvalue $\lambda_2$) and Cplex [29] (for solving (integer) linear programs). All reported computations have been performed on a computer equipped with a 3.70GHz Intel Core i9-10900K processor, 64GB of RAM, and with operating system Fedora 39. Recall that we denote by:

* $LB_{\kappa'}$ the lower bound based on the minimal edge-cuts (Ineq. (1)),
• LB$_{λ_2}$ the lower bound based on the second smallest eigenvalue of the Laplacian matrix of the graph (Ineq. (2)),

• LB$_{Δ}$ the bound based on the maximum degree of the graph (Ineq. (3)),

• LB$_{δ^*}$ the bound based on the degeneracy of the graph (Ineq. (4)),

• LB$_{δ}$ the bound based on the minimum degree of the graph (resp. Ineq. (5)),

• LB$_{Ad}$ the bound based on the average degree of the graph (Ineq. (6)),

• LB$_{Mad}$ the bound based on the maximum average degree (Ineq. (8)),

• C$^*(m, n)$, denoted shortly C$^*$, the bound based on grooming (Ineq. (9)),

• C$^*_{Mad}$ the bound C$^*$ computed on a subgraph of maximum average degree (Ineq. (10)).

Furthermore, we introduce two lower bounds obtained by using the method proposed in [12] for finding an approximation of the maximum average degree of a graph. Let $\sigma_{\delta^*} = (v_1, v_2, \dots, v_n)$ be the elimination ordering of the vertices produced when computing the degeneracy $\delta^*(G)$ of a graph, and let $\bar{X}_i = (v_i, v_{i+1}, \dots, v_n)$ for $1 \le i \le n$ and $G[\bar{X}_i]$ be the subgraph of G induced by $\bar{X}_i$. We have:

$$ \mathrm{cw}(G) \ge C_g^*(m, n) = \max \{C^*(|E_i|, |V_i|) \mid G[\bar{X}_i] = (V_i, E_i), 1 \le i < n\} \quad (11) $$

This bound can be computed in $O(m + n \log n)$ time as the elimination ordering of the vertices, and so the degeneracy $\delta^*$ of a graph, can be computed in $O(n + m)$ time and we call the function $C^*$ after each elimination of a vertex.

Finally, we denote by $C_{g++}^*$ the maximum value obtained when computing $C^*$ on each subgraph created during the execution of the greedy++ algorithm proposed in [11] to obtain a 2-approximation of the maximum average degree. Approximately, this algorithm performs $\log n$ times the procedure for finding the elimination ordering of the degeneracy, but it changes at each iteration the initial weight of the vertices, and so the priorities in the elimination ordering. Let $f^i(v)$ be the weight of vertex $v$ at the beginning of iteration $i$ (initially, $f^1(v) = d_G(v)$). At the beginning of iteration $i$, the algorithm makes a copy $H$ of the graph $G$ and feeds a min-heap data structure $Q$ with the weights $f^i$ of the vertices. Then it iteratively extracts the vertex $v$ of minimum weight from $Q$, set $f^{i+1}(v) = f^i(v) + d_H(v)$, where $d_H(v)$ is the degree of vertex $v$ in the remaining graph $H$, removes vertex $v$ from $H$ and reduces the weight of its neighbors in $Q$. When $H$ is empty, it proceeds with iteration $i+1$. This algorithm has time complexity in $O((m + n \log n) \log n)$ when using a min-heap data structure and running $\log n$ iterations of its main loop, and it performs overall $n \log n$ calls to $C^*$ (one per extraction of a vertex from $Q$).

## 5.2 Two families of graphs

Let $H_k^i$ denote the graph obtained by identifying one vertex of the clique $K_k$ of order $k$ with an extremity of the path $P_i$ of order $i$. Hence, $H_k^0$ is the clique $K_k$, $H_k^1$ is a clique plus a pending edge, $H_k^2$ is a clique with a pending path of length 2, and so on. The graph $H_k^i$ has $k + i$ vertices, $k(k - 1)/2 + i$ edges, diameter $i + 1$, and cutwidth $\mathrm{cw}(H_k^i) = \mathrm{cw}(K_k) = \lceil k^2/4 \rceil$. We have reported in Table 1 the evolution of the lower bounds for $H_{50}^i$ when $i = 0, \dots, 6$. We note that $\mathrm{cw}(H_{50}^i) = 625$ for all $i$.

A first observation is that $\delta(H_k^i) = k$ for $i = 0$ and $1$ when $i \ge 1$. LB$_{λ_2}$ decreases rapidly to 1 when $i$ increases. Indeed, $\lambda_2(G)$ is upper bounded by the vertex- / edge-connectivity of the graph, and so by its minimum degree $\delta(G)$. Hence, we have $\lambda_2(H_k^i) \le 1$ when $i \ge 1$.
Another observation is that bounds that search for a dense subgraph (LB<sub>Mad</sub>, LB<sub>δ*</sub>, C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub>) are independent from *i*. Indeed, we have for all *i* ≥ 0 that LB<sub>Mad</sub>(H<sup>*i*</sup><sub>k</sub>) = LB<sub>Mad</sub>(K<sub>k</sub>) = LB<sub>Ad</sub>(K<sub>k</sub>) = *k*(*k* + 2)/8 and C<sup>*</sup><sub>Mad</sub>(H<sup>*i*</sup><sub>k</sub>) = C<sup>*</sup>(*k*(*k* − 1)/2, *k*) = (*k*<sup>2</sup> − ε)/4, where ε = 1 when *k* is even and 0 otherwise.

285

<table><caption>Table 1: Evolution of the lower bounds for the graphs H<sup>*i*</sup><sub>50</sub> with cw(H<sup>*i*</sup><sub>50</sub>) = 625.</caption><thead><tr><th>Graph</th><th>LB<sub>λ<sub>2</sub></sub></th><th>LB<sub>κ'</sub></th><th>LB<sub>Δ</sub></th><th>LB<sub>δ</sub></th><th>LB<sub>Ad</sub></th><th>LB<sub>Mad</sub></th><th>LB<sub>δ*</sub></th><th>C<sup>*</sup></th><th>C<sup>*</sup><sub>Mad</sub></th><th>C<sup>*</sup><sub>g</sub></th><th>C<sup>*</sup><sub>g++</sub></th></tr></thead><tbody><tr><td>K<sub>50</sub></td><td>625</td><td>49</td><td>25</td><td>625</td><td>325</td><td>325</td><td>625</td><td>625</td><td>625</td><td>625</td><td>625</td></tr><tr><td>H<sup>1</sup><sub>50</sub></td><td>13</td><td>49</td><td>25</td><td>1</td><td>313</td><td>325</td><td>625</td><td>601</td><td>625</td><td>625</td><td>625</td></tr><tr><td>H<sup>2</sup><sub>50</sub></td><td>6</td><td>49</td><td>25</td><td>1</td><td>302</td><td>325</td><td>625</td><td>577</td><td>625</td><td>625</td><td>625</td></tr><tr><td>H<sup>3</sup><sub>50</sub></td><td>3</td><td>49</td><td>25</td><td>1</td><td>291</td><td>325</td><td>625</td><td>552</td><td>625</td><td>625</td><td>625</td></tr><tr><td>H<sup>4</sup><sub>50</sub></td><td>2</td><td>49</td><td>25</td><td>1</td><td>281</td><td>325</td><td>625</td><td>527</td><td>625</td><td>625</td><td>625</td></tr><tr><td>H<sup>5</sup><sub>50</sub></td><td>2</td><td>49</td><td>25</td><td>1</td><td>271</td><td>325</td><td>625</td><td>501</td><td>625</td><td>625</td><td>625</td></tr><tr><td>H<sup>6</sup><sub>50</sub></td><td>1</td><td>49</td><td>25</td><td>1</td><td>262</td><td>325</td><td>625</td><td>475</td><td>625</td><td>625</td><td>625</td></tr></tbody></table>

Let us now consider the graph G(s, n) with *n* vertices, defined in Section 3, where vertex $v_i$ is joined to the *s* vertices $v_{i+h}$, with $1 \le h \le s$ and $i+h \le n$. This graph has $m = sn-s(s+1)/2$ edges, and by construction, we have that cw(G(s, n)) = $s(s+1)/2$ when $n \ge 2s+1$. We have reported in Table 2 the evolution of the lower bounds for G(s, n) when $s = 1, 5, 10, 15, 20$ and $n = 2s+1$.

290

Recall that we have seen in Section 3 that LB<sub>Ad</sub> (the bound of Ineq.(6)) is better than LB<sub>δ*</sub> (the bound of Ineq. (4)) for G(s, n) when *n* is large enough. This is confirmed for $n = 2s + 1$. Furthermore, we observe in Table 2 that the bounds based on grooming perform much better than all other bounds on these graphs, and in fact, we have C<sup>*</sup>(m, n) = cw(G(s, n)) when $n \ge 2s + 1$.

295

<table><caption>Table 2: Evolution of the lower bounds for the graphs G(s, n) for $s = 1, 5, 10, 15, 20$ and $n = 2s + 1$.</caption><thead><tr><th>G(s, n)</th><th>LB<sub>λ<sub>2</sub></sub></th><th>LB<sub>κ'</sub></th><th>LB<sub>Δ</sub></th><th>LB<sub>δ</sub></th><th>LB<sub>Ad</sub></th><th>LB<sub>Mad</sub></th><th>LB<sub>δ*</sub></th><th>C<sup>*</sup></th><th>C<sup>*</sup><sub>Mad</sub></th><th>C<sup>*</sup><sub>g</sub></th><th>C<sup>*</sup><sub>g++</sub></th></tr></thead><tbody><tr><td>G(1, 3)</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>G(5, 11)</td><td>10</td><td>9</td><td>5</td><td>9</td><td>10</td><td>11</td><td>9</td><td>15</td><td>15</td><td>15</td><td>15</td></tr><tr><td>G(10, 21)</td><td>34</td><td>19</td><td>10</td><td>30</td><td>34</td><td>34</td><td>30</td><td>55</td><td>55</td><td>55</td><td>55</td></tr><tr><td>G(15, 31)</td><td>74</td><td>29</td><td>15</td><td>64</td><td>72</td><td>72</td><td>64</td><td>120</td><td>120</td><td>120</td><td>120</td></tr><tr><td>G(20, 41)</td><td>130</td><td>39</td><td>20</td><td>110</td><td>124</td><td>124</td><td>110</td><td>210</td><td>210</td><td>210</td><td>210</td></tr></tbody></table>

## 5.3 Erdős-Rényi random graphs

In this section, we compare the different bounds presented in this paper on Erdős-Rényi random graphs. We start with graphs of order $n = 30$ for which we can also compute the optimal cutwidth (cw). We then consider graphs of order $n = 50$ for which the optimal value is already unreachable.

300

For $n = 30, 50$ and for each density in $p \in [0.05, 0.1, \dots, 0.95]$ (or equivalently for each probability $p \in [0.05, 0.1, \dots, 0.95]$ for the existence of an edge), we have generated 100 Erdős-Rényi random graphs, ensuring that all graphs have the same number $pn(n-1)/2$ of edges. Observe that the *density* of a graph G is measured as $2m/n(n-1)$, and so is different from
its average degree $\text{Ad}(G) = 2m/n$. We have then computed all the bounds and reported in Figures 1 and 2 the average of the computed bounds and running times.

<figure><img src="image_2.png" /><figcaption>Figure 1: Lower bounds and running times (log scale) on Erdős-Rényi graphs ($n = 30$).</figcaption></figure>

In Figure 1a, we observe that $\text{LB}_{\lambda_2}$ dominates all other lower bounds when $p \le 0.75$. Recall that the connectivity threshold for Erdős-Rényi random graphs is $\frac{\log n}{n}$. That is, if $p = p_0 \frac{\log n}{n}$, the graph is asymptotically almost surely connected when $p_0 > 1$, and disconnected when $p_0 < 1$. Hence, when $p_0 < 1$, we have asymptotically almost surely $\lambda_2 = 0$, and so $\text{LB}_{\lambda_2}(G) = 0$. Since in our experiments, we have $n = 30$, and so $\frac{\log 30}{30} \approx 0.11$, most of the graphs we have tested are connected and exhibit the good properties of Erdős-Rényi random graphs for connectivity, small diameter, etc. Furthermore, it has been proved in [30] that when $p_0 > 1$ and for any $\varepsilon > 0$, we have $\lambda_2 = pn + o(n^{\frac{1}{2}+\varepsilon})$ in probability. In other words, the algebraic connectivity $\lambda_2$ of Erdős-Rényi random graphs increases with the (average) degree $pn$. It follows that $\text{LB}_{\lambda_2}$ increases similarly to $pn^2/4$, and this is roughly what we observe in Figure 1a.

We then observe that all the bounds based on grooming ($C^*, C_{\text{Mad}}^*, C_g^*, C_{g++}^*$) dominate all other bounds when $p \ge 0.8$ and finally reach the optimal value of the cutwidth. Moreover, we observe that methods based on grooming provide the same bounds for these graphs. This is due to the properties of Erdős-Rényi random graphs which are such that a subgraph exhibit the same properties as the graph in terms of density, average degree, etc. We will see in Section 5.5 that the situation is different for other families of graphs.

Non surprisingly, we observe that $\text{LB}_{\kappa'}$ not only provides very small lower bounds compared to others, but also requires orders of magnitude more computation time. We also observe that the bounds $\text{LB}_{\text{Mad}}$ and $C_{\text{Mad}}^*$, both based on the maximum average degree, do not provide better bounds than $\text{LB}_{\text{Ad}}$ and $C^*$ respectively, while requiring orders of magnitude more computation time. Hence, bounds relying on the resolution of linear programs seem of little interest for Erdős-Rényi random graphs.

Observe also that we experimentally confirm Proposition 3, that is that $C^*(m, n) \ge \text{LB}_{\text{Ad}}(m, n)$.

The running times reported in Figure 1b reflect the time complexity of the methods: $O(1)$ for $\text{LB}_{\text{Ad}}$; $O(\log n)$ for $C^*$; $O(n)$ for $\text{LB}_{\Delta}$ and $\text{LB}_{\delta}$; $O(m + n \log n)$ for $\text{LB}_{\delta^*}$ and $C_g^*$; $O((m + n \log n) \log n)$ for $C_{g++}^*$; $O(n^{\omega})$ for $\text{LB}_{\lambda_2}$; and much more for $\text{LB}_{\text{Mad}}$, $C_{\text{Mad}}^*$ and $\text{LB}_{\kappa'}$. Moreover, we observe that the time needed to compute the cutwidth of the graphs increases exponentially with the density, and so with the number of edges. This is due to the way the dynamic programming algorithm is implemented in SageMath, as it first searches for the existence of a solution with width $w$ before searching for a solution with width $w + 1$. Fur-
thermore, it starts partitioning the graph into connected components as we have cw(G) = max {cw(G[c]) | c is a connected component of G}. This explains the behavior for low densities since the graphs are not connected.

<figure><img src="image_3.png" /><figcaption>Figure 2: Lower bounds and running times (log scale) on Erdős-Rényi graphs ($n = 50$).</figcaption></figure>

In Figure 2, we have reported for $n = 50$ the bounds on running times for the fastest methods only. We observe the same behaviors than in Figure 1 for the relative qualities of the bounds, except that now $LB_{\lambda_2}$ dominates all other bounds when $p \le 0.8$ instead of 0.75 for $n = 30$.

## 5.4 Interval graphs

We now evaluate our bounds on random (proper) interval graphs. Consider a family $\mathcal{S}$ = $\{S_i | i = 1, 2, ..., n\}$ of intervals on the real line. An interval graph is obtained from $\mathcal{S}$ by creating a vertex $v_i$ for each interval $S_i$ and connecting two vertices $v_i$ and $v_j$ by an edge if the corresponding intervals intersect. An interval graph is proper if not interval in $\mathcal{S}$ contains another interval. That is, if $l_i$ and $r_i$ are the endpoints of interval $S_i$ with $l_i < r_i$, and similarly $l_j < r_j$ are the extremities of $S_j$, we have either $l_j < l_i$ and $r_j < r_i$, or $l_j > l_i$ and $r_j > r_i$.

Using the uniform random generators of (proper) interval graphs available in SageMath, we generated 1000 graphs of order $n = 100$ on which we have computed all the bounds. Then, we have sorted the graphs by increasing number of edges, group them by groups of 5 consecutive graphs, computed the average of the bounds for these groups of 5 graphs and reported the resulting values in Figure 3.

We observe very different results for random (proper) interval graphs than for Erdős-Rényi random graphs. In particular, the bound $LB_{\lambda_2}$ which is very good for for Erdős-Rényi random graphs provides poor bounds on (proper) interval graphs. Indeed, these graphs contain vertices with small degree, as highlighted by the very low values of $LB_{\delta}$, and $LB_{\lambda_2}$ suffers from the presence of vertices with small degree which have a strong impact on the value of the algebraic connectivity, as explained in Section 5.2, that is upper bounded by the edge-connectivity and so by the minimum degree of the graph.

For proper interval graphs (Figure 3a), the best bounds are obtained using $LB_{Mad}$, $LB_{\delta^*}$, $C_{Mad}^*$, $C_g^*$ and $C_{g++}^*$, that is using the methods searching for a dense subgraph. The bound $C_{g++}^*$ seems to offer the best trade-off between the quality of the bound and the time complexity for these graphs.

For interval graphs (Figure 3b), the best bounds are obtained using $C_{Mad}^*$, $C_g^*$ and $C_{g++}^*$. Furthermore, we observe that $C^*$ behaves very well while needing a low computation time.
<figure><img src="image_4.png" /><figcaption>Figure 3: Lower bounds for random (proper) interval graphs with $n = 100$ nodes.</figcaption></figure>

This can be explained by the fact that random interval graphs are generally very dense. Here, the bound $C_g^*$ seems to offer the best trade-off between the quality of the bound and the time complexity for these graphs.

## 5.5 Comparisons with the random graphs used in [24]

We now compare the bounds presented in this paper with the lower bounds obtained in [24] using SDP relaxation. To do so, we have computed our bounds on the graphs used in [24]. These graphs are Erdős-Rényi random graphs and geometric random graphs (i.e., a set of vertices randomly placed on a square of side 1, and two vertices are connected by an edge if at euclidean distance less than $d$).

We have reported in Table 3 the best lower and upper bounds obtained in [24] on Erdős-Rényi random graphs, as well as the corresponding computation time (in seconds). We have also reported the best lower bound found using the methods presented in this paper with the list of methods reaching this bound and the required computation time (in milliseconds). The first two columns of the table corresponds to the number of nodes and the probability $p$ of the existence of an edge. Table 4 presents similarly the results for the geometric random graphs.

For the Erdős-Rényi random graphs (Table 3), we first observe that the results for the bounds of this paper are consistent with the results presented in Section 5.3. More precisely, $LB_{\lambda_2}$ gives very good bounds, but when the density of the graphs is very large, bounds based on grooming ($C^*, C_{\text{Mad}}^*, C_g^*, C_{g++}^*$) are much better. The main observation is that we obtain excellent lower bounds, and most of the time better bounds than those of [24], while the running times of the methods presented in this paper are several orders of magnitude smaller than those of [24].

For the random geometric graphs (Table 4), the methods based on grooming, and in particular $C_{g++}^*$, give the best lower bounds among all the methods presented in this paper. Moreover, these bounds are most of the time better than the bounds of [24] and obtained up to 6 orders of magnitude faster.

Let us mention that an objective of [24] was to propose new methods for getting good lower bounds on dense graphs, but when $p \ge 0.5$, the bounds $LB_{\lambda_2}, C^*, C_{\text{Mad}}^*, C_g^*$ and $C_{g++}^*$ are better and can be computed more quickly.
<table><caption>Table 3: Comparison of the lower bounds based on SDP relaxation obtained in [24] with the bounds obtained using the methods presented in this paper on Erdős-Rényi random graphs. We report the bounds and the running time (in seconds) from [24]. We report the best lower bound that can be obtained using the methods presented in this paper, list the algorithms reaching this bound and report the range of running times of these algorithms (in milliseconds). A single running time is reported when a single algorithm reaches the bound.</caption><thead><tr><th colspan="3">Results from [24]</th><th colspan="4">This paper</th></tr><tr><th>n</th><th>m</th><th>p</th><th>UB</th><th>LB</th><th>Time (sec)</th><th>Best LB</th><th>Algorithms</th><th>Time (ms)</th></tr></thead><tbody><tr><td>20</td><td>60</td><td>0.3</td><td>20</td><td><b>14.27</b></td><td>62.62</td><td>12</td><td>LB<sub>λ2</sub></td><td>1.3940</td></tr><tr><td>20</td><td>81</td><td>0.4</td><td>32</td><td><b>21.54</b></td><td>61.83</td><td>17</td><td>LB<sub>λ2</sub></td><td>1.3888</td></tr><tr><td>20</td><td>85</td><td>0.5</td><td>31</td><td><b>21.92</b></td><td>63.94</td><td>16</td><td>LB<sub>δ*</sub>, C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.1760, 3.1173]</td></tr><tr><td>20</td><td>124</td><td>0.6</td><td>52</td><td>36.40</td><td>63.38</td><td><b>39</b></td><td>LB<sub>λ2</sub></td><td>1.4482</td></tr><tr><td>20</td><td>130</td><td>0.7</td><td>56</td><td>38.65</td><td>63.59</td><td><b>41</b></td><td>C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.2275, 0.6764]</td></tr><tr><td>20</td><td>149</td><td>0.8</td><td>68</td><td>46.59</td><td>62.43</td><td><b>59</b></td><td>C<sup>*</sup>, C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.0172, 5.1172]</td></tr><tr><td>20</td><td>177</td><td>0.9</td><td>88</td><td>59.47</td><td>59.05</td><td><b>87</b></td><td>C<sup>*</sup>, C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.0184, 5.3825]</td></tr><tr><td>30</td><td>131</td><td>0.3</td><td>44</td><td><b>30.69</b></td><td>365.83</td><td>25</td><td>LB<sub>λ2</sub></td><td>1.7538</td></tr><tr><td>30</td><td>166</td><td>0.4</td><td>60</td><td><b>41.79</b></td><td>370.88</td><td>40</td><td>LB<sub>λ2</sub></td><td>1.4968</td></tr><tr><td>30</td><td>222</td><td>0.5</td><td>87</td><td>60.55</td><td>376.59</td><td><b>69</b></td><td>LB<sub>λ2</sub></td><td>1.7805</td></tr><tr><td>30</td><td>253</td><td>0.6</td><td>101</td><td>70.84</td><td>400.35</td><td><b>76</b></td><td>LB<sub>λ2</sub></td><td>1.5504</td></tr><tr><td>30</td><td>305</td><td>0.7</td><td>135</td><td>91.86</td><td>379.24</td><td><b>96</b></td><td>C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.2944, 1.4577]</td></tr><tr><td>30</td><td>353</td><td>0.8</td><td>161</td><td>110.58</td><td>401.19</td><td><b>143</b></td><td>C<sup>*</sup>, C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.0196, 12.4459]</td></tr><tr><td>30</td><td>376</td><td>0.9</td><td>176</td><td>119.93</td><td>392.83</td><td><b>166</b></td><td>C<sup>*</sup>, C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.0193, 12.7959]</td></tr><tr><td>40</td><td>246</td><td>0.3</td><td>92</td><td><b>60.12</b></td><td>1505.80</td><td>46</td><td>LB<sub>λ2</sub></td><td>2.0754</td></tr><tr><td>40</td><td>325</td><td>0.4</td><td>126</td><td><b>85.52</b></td><td>1597.97</td><td>81</td><td>LB<sub>λ2</sub></td><td>1.9107</td></tr><tr><td>40</td><td>365</td><td>0.5</td><td>155</td><td><b>99.75</b></td><td>1495.82</td><td>95</td><td>LB<sub>λ2</sub></td><td>2.0809</td></tr><tr><td>40</td><td>458</td><td>0.6</td><td>195</td><td>130.84</td><td>1593.94</td><td><b>149</b></td><td>LB<sub>λ2</sub></td><td>2.2204</td></tr><tr><td>40</td><td>524</td><td>0.7</td><td>235</td><td>115.30</td><td>1691.67</td><td><b>194</b></td><td>LB<sub>λ2</sub></td><td>2.0056</td></tr><tr><td>40</td><td>610</td><td>0.8</td><td>281</td><td>187.95</td><td>1723.79</td><td><b>230</b></td><td>C<sup>*</sup>, C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.0212, 21.0202]</td></tr><tr><td>40</td><td>704</td><td>0.9</td><td>346</td><td>227.74</td><td>1703.14</td><td><b>324</b></td><td>C<sup>*</sup>, C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.0567, 24.4861]</td></tr><tr><td>50</td><td>372</td><td>0.3</td><td>159</td><td><b>91.92</b></td><td>5310.93</td><td>85</td><td>LB<sub>λ2</sub></td><td>95.2239</td></tr><tr><td>50</td><td>506</td><td>0.4</td><td>211</td><td>133.61</td><td>5404.70</td><td><b>156</b></td><td>LB<sub>λ2</sub></td><td>2.3170</td></tr><tr><td>50</td><td>647</td><td>0.5</td><td>286</td><td>182.44</td><td>5313.71</td><td><b>198</b></td><td>LB<sub>λ2</sub></td><td>2.4786</td></tr><tr><td>50</td><td>754</td><td>0.6</td><td>338</td><td>221.14</td><td>5511.51</td><td><b>271</b></td><td>LB<sub>λ2</sub></td><td>2.7552</td></tr><tr><td>50</td><td>850</td><td>0.7</td><td>382</td><td>253.98</td><td>5552.34</td><td><b>309</b></td><td>LB<sub>λ2</sub></td><td>2.7530</td></tr><tr><td>50</td><td>998</td><td>0.8</td><td>468</td><td>312.20</td><td>6303.39</td><td><b>398</b></td><td>C<sup>*</sup>, C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.0403, 33.3912]</td></tr><tr><td>50</td><td>1092</td><td>0.9</td><td>525</td><td>350.87</td><td>6033.16</td><td><b>492</b></td><td>C<sup>*</sup>, C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.0200, 36.4516]</td></tr></tbody></table>
<table><caption>Table 4: Comparison of the lower bounds based on SDP relaxation obtained in [24] with the bounds obtained using the methods presented in this paper on random geometric graphs. We report the bounds and the running time (in seconds) from [24]. We report the best lower bound that can be obtained using the methods presented in this paper, list the algorithms reaching this bound and report the range of running times of these algorithms (in milliseconds). A single running time is reported when a single algorithm reaches the bound.</caption><thead><tr><th colspan="4">Results from [24]</th><th colspan="3">This paper</th></tr><tr><th>n</th><th>m</th><th>d</th><th>UB</th><th>LB</th><th>Time (sec)</th><th>Best LB</th><th>Algorithms</th><th>Time (ms)</th></tr></thead><tbody><tr><td>20</td><td>34</td><td>0.3</td><td>7</td><td>5.24</td><td>42.55</td><td><b>7</b></td><td>C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.3238, 1.6108]</td></tr><tr><td>20</td><td>54</td><td>0.4</td><td>12</td><td>8.28</td><td>42.69</td><td><b>12</b></td><td>LB<sub>δ*</sub>, C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.1600, 2.1939]</td></tr><tr><td>20</td><td>80</td><td>0.5</td><td>22</td><td><b>16.50</b></td><td>61.18</td><td>15</td><td>C<sup>*</sup><sub>g++</sub></td><td>0.4959</td></tr><tr><td>20</td><td>84</td><td>0.6</td><td>21</td><td>16.56</td><td>57.48</td><td><b>18</b></td><td>C<sup>*</sup><sub>g++</sub></td><td>0.4826</td></tr><tr><td>20</td><td>137</td><td>0.7</td><td>55</td><td>39.83</td><td>58.37</td><td><b>53</b></td><td>C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.2458, 4.7052]</td></tr><tr><td>20</td><td>173</td><td>0.8</td><td>83</td><td>56.75</td><td>62.43</td><td><b>83</b></td><td>C<sup>*</sup>, C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.0191, 5.2438]</td></tr><tr><td>20</td><td>158</td><td>0.9</td><td>69</td><td>48.57</td><td>59.91</td><td><b>68</b></td><td>C<sup>*</sup>, C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.0172, 5.1551]</td></tr><tr><td>30</td><td>83</td><td>0.3</td><td>13</td><td>10.46</td><td>293.96</td><td><b>13</b></td><td>C<sup>*</sup><sub>g++</sub></td><td>0.6435</td></tr><tr><td>30</td><td>154</td><td>0.4</td><td>45</td><td><b>32.72</b></td><td>337.93</td><td>30</td><td>C<sup>*</sup><sub>g++</sub></td><td>0.9339</td></tr><tr><td>30</td><td>210</td><td>0.5</td><td>72</td><td>51.65</td><td>346.9</td><td><b>67</b></td><td>C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g++</sub></td><td>[1.1430, 7.3059]</td></tr><tr><td>30</td><td>327</td><td>0.6</td><td>126</td><td>92.20</td><td>373.08</td><td><b>123</b></td><td>C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.3982, 1.5669]</td></tr><tr><td>30</td><td>304</td><td>0.7</td><td>119</td><td>84.98</td><td>395.81</td><td><b>97</b></td><td>C<sup>*</sup><sub>g++</sub></td><td>1.4546</td></tr><tr><td>30</td><td>408</td><td>0.8</td><td>200</td><td>134.97</td><td>391.51</td><td><b>198</b></td><td>C<sup>*</sup>, C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.0207, 12.2125]</td></tr><tr><td>30</td><td>417</td><td>0.9</td><td>207</td><td>139.47</td><td>381.37</td><td><b>207</b></td><td>C<sup>*</sup>, C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.0200, 12.1496]</td></tr><tr><td>40</td><td>167</td><td>0.3</td><td>31</td><td><b>22.48</b></td><td>1 253.51</td><td>22</td><td>C<sup>*</sup><sub>g++</sub></td><td>1.3340</td></tr><tr><td>40</td><td>243</td><td>0.4</td><td>50</td><td><b>39.98</b></td><td>1 389.39</td><td>35</td><td>C<sup>*</sup><sub>g++</sub></td><td>1.7180</td></tr><tr><td>40</td><td>340</td><td>0.5</td><td>92</td><td><b>69.41</b></td><td>1 353.95</td><td>58</td><td>C<sup>*</sup><sub>g++</sub></td><td>2.1372</td></tr><tr><td>40</td><td>431</td><td>0.6</td><td>126</td><td>97.37</td><td>1 416.42</td><td><b>107</b></td><td>C<sup>*</sup><sub>g++</sub></td><td>2.4588</td></tr><tr><td>40</td><td>576</td><td>0.7</td><td>238</td><td>165.83</td><td>1 650.37</td><td><b>205</b></td><td>C<sup>*</sup><sub>g++</sub></td><td>3.1359</td></tr><tr><td>40</td><td>654</td><td>0.8</td><td>294</td><td>201.33</td><td>1 669.65</td><td><b>274</b></td><td>C<sup>*</sup>, C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.0205, 20.6606]</td></tr><tr><td>40</td><td>742</td><td>0.9</td><td>366</td><td>245.12</td><td>1 758.20</td><td><b>362</b></td><td>C<sup>*</sup>, C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.0196, 21.9421]</td></tr><tr><td>50</td><td>314</td><td>0.3</td><td>63</td><td>48.00</td><td>3 534.43</td><td><b>57</b></td><td>C<sup>*</sup><sub>g++</sub></td><td>2.2986</td></tr><tr><td>50</td><td>467</td><td>0.4</td><td>131</td><td><b>96.25</b></td><td>4 139.52</td><td>94</td><td>C<sup>*</sup><sub>g++</sub></td><td>3.0117</td></tr><tr><td>50</td><td>580</td><td>0.5</td><td>175</td><td><b>127.56</b></td><td>4 433.95</td><td>121</td><td>C<sup>*</sup><sub>g++</sub></td><td>3.4204</td></tr><tr><td>50</td><td>749</td><td>0.6</td><td>266</td><td><b>189.41</b></td><td>4 604.08</td><td>182</td><td>C<sup>*</sup><sub>g++</sub></td><td>4.2415</td></tr><tr><td>50</td><td>936</td><td>0.7</td><td>398</td><td>272.53</td><td>5 064.41</td><td><b>347</b></td><td>C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.8366, 5.0154]</td></tr><tr><td>50</td><td>963</td><td>0.8</td><td>416</td><td>283.43</td><td>5 512.39</td><td><b>368</b></td><td>C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.8130, 5.0299]</td></tr><tr><td>50</td><td>1 136</td><td>0.9</td><td>556</td><td>368.44</td><td>6 983.07</td><td><b>536</b></td><td>C<sup>*</sup>, C<sup>*</sup><sub>Mad</sub>, C<sup>*</sup><sub>g</sub>, C<sup>*</sup><sub>g++</sub></td><td>[0.0226, 35.0571]</td></tr></tbody></table>
# 6 Conclusion

In this article we have given new lower bounds for the cutwidth of a graph which are of interest to design faster branch-and-bound algorithms. In particular, we have given bounds using the grooming on a path which appear to be in many cases than bounds in the literature. Furthermore, bounds based on grooming can be computed quickly. This raises the question whether better bounds can be obtained using the methods proposed in [24], using semidefinite programming, if given as input the bounds presented in this paper.

# References

[1] Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, and Ohad Trabelsi. Breaking the cubic barrier for all-pairs max-flow: Gomory-hu tree in nearly quadratic time. In *63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS)*, pages 884–895. IEEE, 2022.

[2] Udo Adamy, Christoph Ambühl, R. Sai Anand, and Thomas Erlebach. Call control in rings. *Algorithmica*, 47(3):217–238, 2007.

[3] Donald L. Adolphson and Te Chiang Hu. Optimal linear ordering. *SIAM Journal on Applied Mathematics*, 25(3):403–423, 1973.

[4] Nikhil Bansal, Dor Katzelnick, and Roy Schwartz. On approximating cutwidth and path-width. *CoRR*, abs/2311.15639, 2023.

[5] Dominique Barth, François Pellegrini, André Raspaud, and Jean Roman. On bandwidth, cutwidth, and quotient graphs. *RAIRO-Theoretical Informatics and Applications*, 29(6):487–508, 1995.

[6] Stefan Behnel, Robert Bradshaw, Craig Citro, Lisandro Dalcin, Dag Sverre Seljebotn, and Kurt Smith. Cython: The best of both worlds. *Computing in Science Engineering*, 13(2):31–39, march-april 2011.

[7] Jean-Claude Bermond, Laurent Braud, and David Coudert. Traffic Grooming on the Path. *Theoretical Computer Science*, 384(2-3):139–151, 2007.

[8] Jean-Claude Bermond, Michel Cosnard, David Coudert, and Frédéric Havet. Groupage sur le chemin pour borner la largeur de coupe. In *AlgoTel 2023 - 25èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications*, page 4, Cargese, France, May 2023.

[9] Jean-Claude Bermond, Michel Cosnard, David Coudert, and Stephane Perennes. Maximum number of requests on a path with a given grooming factor. Technical report, hal-04736088, October 2024. A preliminary version was presented at the Advanced International Conference on Telecommunications (AICT), Le Gosier, Guadeloupe, France, 2006, IEEE.

[10] Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Dimitrios M. Thilikos. A note on exact algorithms for vertex ordering problems on graphs. *Theory of Computing Systems*, 50(3):420–432, 2012.

[11] Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos E. Tsourakakis, Di Wang, and Junxing Wang. Flowless: Extracting densest subgraphs without flow computations. In *The Web Conference (WWW)*, pages 573–583. ACM / IW3C2, 2020.
440

[12] Moses Charikar. Greedy approximation algorithms for finding dense components in a graph. In *3rd International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX)*, volume 1913 of *Lecture Notes in Computer Science*, pages 84–95. Springer, 2000.

445

[13] Chandra Chekuri, Kent Quanrud, and Manuel R. Torres. Densest subgraph: Supermodularity, iterative peeling, and flow. In *ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 1531–1555. SIAM, 2022.

[14] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In *63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS)*, pages 612–623. IEEE, 2022.

450

[15] Nathann Cohen. *Three years of graphs and music : some results in graph theory and its applications*. PhD thesis, University of Nice Sophia Antipolis, France, 2011.

[16] David Coudert. A note on Integer Linear Programming formulations for linear ordering problems on graphs. Research Report hal-01271838, Inria ; I3S ; Universite Nice Sophia Antipolis ; CNRS, February 2016.

455

[17] Elizabeth Cuthill and James McKee. Reducing the bandwidth of sparse symmetric matrices. In *ACM '69: Proceedings of the 1969 24th national conference*, pages 157–172, 1969.

[18] Alexander Keewatin Dewdney. The bandwidth of a graph: Some recent results. In *Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing*, number 17, pages 273–288, 1976.

[19] Josep Díaz, Jordi Petit, and Maria Serna. A survey on graph layout problems. *ACM Computing Surveys*, 34(3):313–356, 2002.

460

[20] Josep Díaz, Maria Serna, Paul Spirakis, and Jacobo Torán. *Paradigms for fast parallel approximability*. Cambridge University Press, 1997.

[21] Krzystof Diks, Hristo N. Djidjev, Ondrej Sykora, and Imrich Vrto. Edge separators for planar graphs and their applications. *Journal of Algorithms*, 14:258–279, 1993.

465

[22] Ulrich Elsner. *Graph Partitioning: A Survey*. Preprintreihe des Chemnitzer SFB 393/97-27. Technishe Universität Chemnitz, 1997.

[23] Miroslav Fiedler. Algebraic connectivity of graphs. *Czechoslovak Mathematical Journal*, 23(2):298–305, 1973.

[24] Elisabeth Gaar, Diane Puges, and Angelika Wiegele. Strong SDP based bounds on the cutwidth of a graph. *Computers & Operations Research*, 161:106449, 2024.

470

[25] Giorgio Gallo, Michael D. Grigoriadis, and Robert E. Tarjan. A fast parametric maximum flow algorithm and applications. *SIAM Journal on Computing*, 18(1):30–55, 1989.

[26] Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna. Cutwidth: Obstructions and algorithmic aspects. *Algorithmica*, 81:557–588, 2019.

475

[27] Andrew Vladislav Goldberg. Finding a maximum density subgraph. *University of California Berkeley*, 1984.
[28] Ralph Edward Gomory and Te Chiang Hu. Multi-terminal network flows. *Journal of the Society for Industrial and Applied Mathematics*, 9(4):551–570, 1961.

480

[29] IBM ILOG. CPLEX Optimization Studio 22.1.1. https://www-01.ibm.com/software/integration/optimization/cplex-optimizer/.

[30] Ferenc Juhász. The asymptotic behaviour of Fiedler's algebraic connectivity for random graphs. *Discrete Mathematics*, 96(1):59–63, 1991.

[31] Martin Juvan and Bojan Mohar. Optimal linear labelings and eigenvalues of graphs. *Discrete Applied Mathematics*, 36(2):153–168, 1992.

485

[32] Samir Khuller and Barna Saha. On finding dense subgraphs. In *36th International Colloquium on Automata, Languages and Programming (ICALP)*, volume 5555 of *Lecture Notes in Computer Science*, pages 597–608. Springer, 2009.

[33] Benoît R. Kloeckner. Cutwidth and degeneracy of graphs. arXiv 0907.5138, 2010.

[34] Richard B. Lehoucq, Danny C. Sorensen, and Chao Yang. *ARPACK users' guide - solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods*. Software, environments, tools. SIAM, 1998.

490

[35] Rafael Martí, Juan J. Pantrigo, Abraham Duarte, and Eduardo G. Pardo. Branch and bound for the cutwidth minimization problem. *Computers & Operations Research*, 40(1):137–149, 2013.

[36] David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. *Journal of the Association for Computing Machinery*, 30(3):417–427, jul 1983.

495

[37] Bojan Mohar. The laplacian spectrum of graphs. In *Graph Theory, Combinatorics, and Applications, Vol. 2. Proceedings of the sixth quadrennial international conference on the theory and applications of graphs held at Western Michigan University, Kalamazoo, MI, USA, May 30-June 3, 1988*, pages 871–898. Wiley, 1991.

500

[38] Jaroslav Nešetřil and Patrice Ossona De Mendez. *Sparsity: graphs, structures, and algorithms*, volume 28. Springer Science & Business Media, 2012.

[39] Victor Y. Pan and Zhao Q. Chen. The complexity of the matrix eigenproblem. In *Annual ACM Symposium on Theory of Computing (STOC)*, pages 507–516. ACM, 1999.

505

[40] The Sage Developers. *SageMath, the Sage Mathematics Software System (Version 10.4)*, 2024. https://www.sagemath.org.

[41] Dimitrios M. Thilikos, Maria J. Serna, and Hans L. Bodlaender. Cutwidth I: A linear time fixed parameter algorithm. *Journal of Algorithms*, 56(1):1–24, 2005.

[42] Charalampos E. Tsourakakis, Francesco Bonchi, Aristides Gionis, Francesco Gullo, and Maria A. Tsiarli. Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees. In *The 19th ACM SIGKDD International Conference on Knowledge Discovery (KDD)*, pages 104–112. ACM, 2013.

510

[43] Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha to omega. In *ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 3792–3835. SIAM, 2024.

515
520

525

[44] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, İlhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. *Nature Methods*, 17:261–272, 2020.