Improved Lower Bounds for the Cyclic Bandwidth Problem

Abstract

We study the classical Cyclic Bandwidth problem, an optimization problem which takes as input an undirected graph $G=(V,E)$ with $|V|=n$, and asks for a labeling $\varphi$ of V in which every vertex v takes a unique value $\varphi (v)\in [1;n]$, in such a way that $B_c(G,\varphi )=\max \{\min _{uv\in E(G)}\{|\varphi (u)-\varphi (v)|,n-|\varphi (u)-\varphi (v)|\}\}$, called the cyclic bandwidth of G, is minimized.

We provide three new and improved lower bounds for the Cyclic Bandwidth problem, applicable to any graph G: two are based on the neighborhood vertex density of G, the other one on the length of a longest cycle in a cycle basis of G. We also show that our results improve the best known lower bounds for a large proportion of a set of instances taken from a frequently used benchmark, the Harwell-Boeing sparse matrix collection. Our third proof provides additional elements: first, an improved sufficient condition yielding $B_c(G)=B(G)$ (where $B(G)=\min _{\varphi }\{\max _{uv\in E(G)}\{|\varphi (u)-\varphi (v)|\}\}$ denotes the bandwidth of G) ; second, an algorithm that, under some conditions, computes a labeling reaching B(G) from a labeling reaching $B_c(G)$.

1 Introduction

Let $G=(V,E)$ be an undirected graph without loops and multiple edges. Let $|V|=n$, and let $\varphi$ be a bijection from V to [n], where [n] denotes the set $\{1,2,3\ldots n\}$. In the rest of the paper, $\varphi$ will be called a cb-labeling of G (where “cb” stands for “cyclic bandwidth”). For any value $p\in \mathbb {Z}$, we let $|p|_n=\min \{|p|,n-|p|\}$. The Cyclic Bandwidth of G induced by $\varphi$, which we denote $B_c(G,\varphi )$, is defined as follows: $B_c(G,\varphi ) = \max _{uv\in E} \{|\varphi (u)-\varphi (v)|_n\}$. The Cyclic Bandwidth of a graph G, denoted $B_c(G)$, is the minimum value $B_c(G,\varphi )$ among all possible labelings $\varphi$, and such a labeling will be called an optimal cb-labeling. We are now ready to define the Cyclic Bandwidth problem, which is the following optimization problem: given a graph $G=(V,E)$ with n vertices, find $B_c(G)$. In the following, we shall denote by $\varphi ^*$ any optimal cb-labeling of G, i.e., any labeling of G satisfying $B_c(G,\varphi ^*)=B_c(G)$.

The Cyclic Bandwidth problem has been introduced in [6], in the context of designing a ring interconnection network between computers. It can be seen as a variant of the well-known Bandwidth Minimization problem, whose formal introduction is due to Harper [3] in 1964 – see also the survey from Chinn et al. [1] for a more detailed historical account. The Bandwidth Minimization problem also asks for a bm-labeling $\varphi$ (where “bm” stands for “bandwidth minimization”), i.e., a bijection from V to [n]. The value computed from $\varphi$ is in that case $B(G,\varphi )=\max _{uv\in E} \{|\varphi (u)-\varphi (v)|\}$. The Bandwidth Minimization problem asks for a labeling $\varphi ^*$ such that $B(G,\varphi ^*)$ is minimized, and the latter value is denoted B(G). Any optimal labeling will be called an optimal bm-labeling of G. Note that there is a strong connection between B(G) and $B_c(G)$, starting with the trivial fact that for any graph G, $B_c(G)\le B(G)$.

The Cyclic Bandwidth has been extensively studied. It has been shown to be NP-hard, even in the case of trees with maximum degree 3 [8]. The value of $B_c(G)$ has also been determined when G belongs to a specific class of graphs, e.g., paths, cycles, Cartesian products of paths (resp. of cycles, of paths and cycles), full k-ary trees, complete graphs, complete bipartite graphs, and unit interval graphs [2, 4, 7, 8]. Some other works studied the relationship between $B_c(G)$ and B(G), and notably aimed at determining sufficient conditions under which the equality $B(G)=B_c(G)$ holds [5, 9]. In particular, it has been shown that $B(T)=B_c(T)$ for any tree T [4]. Another set of results is concerned with determining bounds for $B_c(G)$, and notably lower bounds, for general graphs [15]. First, it is easy to see that for any graph G, $B_c(G)\ge \frac{\varDelta (G)}{2}$, where $\varDelta (G)$ denotes the maximum degree of G. Besides, for any graph G, we have $\frac{B(G)}{2}\le B_c(G)\le B(G)$, the leftmost bound being from [9]. Other lower bounds have been obtained, most of these results being based on the density or on a relevant cycle basis of the studied graph (see, e.g., [4, 15] which are in connection with our results).

Finally, more recent papers are concerned with designing efficient heuristics for the Cyclic Bandwidth problem (see, e.g., [12,13,14]) where both execution time and upper bounds for $B_c(G)$ are examined – the latter being tested on a subset of the classical Harwell-Boeing sparse matrix collection (see, e.g., https://math.nist.gov/MatrixMarket/collections/hb.html).

Our goal in this paper is to provide lower bounds for $B_c(G)$ that apply to any graph G. We essentially prove three lower bounds: two of them rely on the graph density (Theorems 1 and 3), and both improve the best known results; the third one relies on a relevant cycle basis for G (Theorem 9), and also improves the best known related result. The latter result also presents improved sufficient conditions under which $B_c(G)=B(G)$, and provides a relabeling algorithm which, under these conditions, and given a cb-labeling $\varphi$ of G, computes a bm-labeling $\varphi '$ of G such that $B_c(G,\varphi )=B(G,\varphi ')$. We also successfully applied our results to a benchmark of 28 Harwell-Boeing graphs.

This paper is organized as follows: in Sect. 2 we discuss our graph density lower bounds, and in Sect. 3 our lower bound based on a relevant cycle basis of G. Section 4 describes our results on the abovementioned benchmark.

2 Graph Density Lower Bounds

In this section, we present, in Theorems 1 and 3, two new lower bounds on $B_c(G)$ that apply to any graph G. As discussed later, they can be seen as generalizations of previously existing lower bounds.

Theorem 1

Let G be a graph, v any vertex of G, and $i\ge 1$ an integer. Let $N_i(v)$ denote the set of vertices within distance i from v in G. Then we have $B_c(G) \ge \left\lceil \frac{|N_i(v)|-1}{2i}\right\rceil$.

In order to prove Theorem 1, the following lemma is needed.

Lemma 2

Let $d\ge 0$ be an integer, and let ${u_0,u_1,\ldots ,u_d}$ be a path of length d in G. Let $\varphi ^*$ be an optimal cb-labeling of G. Then, $|\varphi ^*(u_d)-\varphi ^*(u_0)|_{n}\le d\cdot B_c(G)$.

Proof

First, note that $|x-y|_n$ satisfies the triangle inequality. Since $\varphi ^*$ is an optimal cb-labeling of G, by definition we have $|\varphi ^*(u_{i+1})-\varphi ^*(u_i)|_{n}\le B_c(G)$ for any $0\le i<d$. Consequently, summing the above expression for all $0\le i<d$ yields the required result.   $\square$

Proof

(of Theorem 1). Let $i\ge 1$ be an integer, and recall that $N_i(v)$ denotes the set of vertices lying at distance less than or equal to i from v in G. Let $\varphi ^*$ be an optimal cb-labeling of G, and by extension let $\varphi ^*(N_i(v))$ be the set of labels used by $\varphi ^*$ to label the vertices of $N_i(v)$. From Lemma 2 we conclude that $\varphi ^*(N_i(v))\subseteq [ \varphi ^*(v)-i\cdot B_c(G);\varphi ^*(v)+i\cdot B_c(G)]$ mod n, since for any vertex $u\in N_i(v)$ there exists a path of length at most i between v and u.

The above interval $[\varphi ^*(v)-i\cdot B_c(G);\varphi ^*(v)+i\cdot B_c(G)]$ mod n contains $2i\cdot B_c(G)+1$ distinct values. Since $\varphi ^*$ is injective, we have that $|N_i(v)|\le 2i\cdot B_c(G)+1$, which concludes the proof.    $\square$

Note that Theorem 1 generalizes the trivial lower bound $B_c(G)\ge \left\lceil \frac{\varDelta (G)}{2} \right\rceil$ (where $\varDelta (G)$ denotes the maximum degree of G): take for this $i=1$ and any vertex v of degree $\varDelta (G)$. Our second result has the same flavor as Theorem 1 above. However, instead of relying on $N_i(v)$, it considers the number of vertices that lie at distance at most i from either one of two vertices u or v of G, where $uv\in E(G)$.

Theorem 3

Let $G=(V,E)$ be a graph, u and v two distinct vertices of G, $i\ge 1$ an integer, and $N_i(u,v)$ the set of vertices within distance i from either u or v in G. Then, for every edge $uv\in E$, we have $B_c(G) \ge \left\lceil \frac{|N_i(u,v)|-1}{2i+1}\right\rceil$.

Proof

The arguments are somewhat similar to those used in proof of Theorem 1. Take any edge $uv\in E(G)$, and observe an optimal cb-labeling $\varphi ^*$ of G. First, note that $|\varphi ^*(u)-\varphi ^*(v)|_n\le B_c(G)$ by definition. Moreover, by Lemma 2, we know that the set of labels used by $\varphi ^*$ to label the vertices of $N_i(u,v)$ is included in a closed interval of size $(2i+1)\cdot B_c(G)$, since any two vertices of $N_i(u,v)$ are connected by a path of length at most $2i+1$. Since $\varphi ^*$ is injective, we conclude from the above that $|N_i(u,v)|\le (2i+1)\cdot B_c(G)+1$, which proves the result.   $\square$

We note that, although Theorems 1 and 3 look similar, none of these two results strictly contains the other. Note also that Theorem 3 generalizes a result for lower bounds on trees proved in [8]. Due to lack of space, the above two claims are not proved here. We finally note that the lower bounds of Theorems 1 and 3 are tight for several well-known classes of graphs, such as paths, cycles, complete graphs, and caterpillars.

3 Cycle Basis Lower Bound

The whole current section is devoted to proving Theorem 9, which provides a lower bound for $B_c(G)$ based on both B(G) and the length $\ell$ of the longest cycle in a cycle basis of G. Theorem 9 also gives an improved sufficient condition under which $B_c(G)=B(G)$, also based on $\ell$. Theorem 9 can be considered as somewhat similar to Theorem 3.1 from [4], but is actually different as it provides a lower bound for $B_c(G)$.

Another interesting point is that, on the way to proving Theorem 9, we also prove the following result, of independent interest: there exists a labeling algorithm (namely, Algorithm 1) that, when $\ell <\frac{n}{B_c(G)}$, computes a bm-labeling $\varphi '$ of G starting from a cb-labeling $\varphi$ of G, such that $B(G,\varphi ')\le B_c(G,\varphi )$. In particular, if $\varphi$ is optimal, so is $\varphi '$, and thus $B_c(G)=B(G)$. The interest of Algorithm 1 lies in the fact that, when $\ell <\frac{n}{B_c(G)}$, a labeling $\varphi$ satisfying $B_c(G,\varphi )=k$ does not necessarily satisfy $B(G,\varphi )=k$ – and in that case another labeling $\varphi '$ is needed in order to reach $B(G,\varphi ')=k$.

Theorem 9 relies on Lemma 7, which we prove first. Before that, we start with some definitions.

Definition 4

Let $G_1$ and $G_2$ two graphs such that $V(G_1)=V(G_2)=V$. The pairwise symmetric difference of $G_1$ and $G_2$, denoted $psd(G_1,G_2)$, is the graph $G'$ whose set of vertices is V, and whose edges are those belonging to exactly one of the two graphs $G_1$ and $G_2$. By extension, the symmetric difference $sd(\mathcal {G})$ of a set $\mathcal {G}=\{G_1,G_2\ldots G_p\}$ of graphs, each built on the same set V of vertices, is $psd(G_1,psd(G_2(\ldots psd(G_{p-1},G_p)))$.

Definition 5

A cycle basis of a graph G is a set of cycles $\mathcal {C}$ of G such that any cycle of G either belongs to $\mathcal {C}$ or can be obtained by symmetric difference of a subset of $\mathcal {C}$.

Finally, we use a definition from [4], which will prove useful in the following.

Definition 6

Given a graph $G=(V,E)$, let $S\subset V\times V$ be such that $(u,v)\in S$ iff $uv\in E(G)$. Let $\varphi$ be a cb-labeling of V, and let $\alpha _\varphi : S \rightarrow \{-1,0,1\}$ denote the following function:

$$\alpha _\varphi (u,v)=\left\{ \begin{array}{lll} 0&{}\text {if}&{} |\varphi (u)-\varphi (v)|\le B_c(G,\varphi )\\ 1&{}\text {if}&{} \varphi (u)-\varphi (v)\ge n-B_c(G,\varphi )\\ -1&{}\text {if}&{} \varphi (u)-\varphi (v)\le B_c(G,\varphi )-n \end{array}\right. $$

In other words, $\alpha _\varphi (u,v)=0$ whenever u and v have “close enough labels”. Otherwise, $\alpha _\varphi (u,v)=\pm 1$, depending on which vertex among u and v has the greatest label. Hence, $\alpha _\varphi$ is not symmetric, since for any edge uv in E(G), $\alpha _\varphi (u,v)=-\alpha _\varphi (v,u)$. In the following, we will say that an edge $uv \in E(G)$ has a zero $\alpha _\varphi$ when $\alpha _\varphi (u,v)=0$, and a non-zero $\alpha _\varphi$ otherwise.

Fig. 1.

Illustration of Definition 6 on a graph G with $n=9$ with a cb-labeling $\varphi$ such that $B_c(G,\varphi )=4$. Each edge uv crossing the dashed vertical line has a non-zero $\alpha _\varphi (u,v)$.

Fig. 1 illustrates the above definition. This figure represents a graph G with $n=9$ vertices, together with a cb-labeling $\varphi$ satisfying $B_c(G,\varphi )=4$ (note that $\varphi$ is not optimal, since $B(G)=2$ in this case). Vertices of G are displayed along a cycle, ordered (clockwise) by their labels in $\varphi$. For readability, we assume that labels and vertex identifiers are the same.

It can be seen that all edges having a non-zero $\alpha _\varphi$ are the ones that cross the dashed vertical line – because that line separates edges whose end vertices carry labels that are strictly more than $B_c(G,\varphi )=4$ apart. The important thing to notice here is that, for any edge uv of G, the sign of the corresponding $\alpha _\varphi$ depends in which direction the dashed line is crossed, for example $\alpha _\varphi (7,2)=\alpha _\varphi (8,1)=\alpha _\varphi (9,1)=1$ (the dashed line is crossed from left to right), while $\alpha _\varphi (2,7)=\alpha _\varphi (1,8)=\alpha _\varphi (1,9)=-1$ (the dashed line is crossed from right to left). In other words, when computing $\alpha _\varphi (u,v)$ for an edge $uv\in E(G)$, an orientation is given to that edge.

Let us define $s_\alpha (C)=\alpha _\varphi (x_p,x_0) + \sum _{i=0}^{p-1}\alpha _\varphi (x_i,x_{i+1})$ for any cycle $C=(x_0,x_1,\ldots x_p,x_0)$ of G, and let us call $s_\alpha (C)$ the $\alpha$-sum of C).

It can then be seen that, if $C_1$ and $C_2$ are two cycles in G, and if $C=psd(C_1,C_2)$ is also a cycle, not all edges of C necessarily have the same orientation (induced by $\alpha _\varphi$) as in $C_1$ or $C_2$. Such a case is illustrated in Fig. 2, where, e.g., the edge connecting vertices 2 and 5 in $C_1$ (left) is oriented from 2 to 5 in the $\alpha$-sum of $C_1$, while in $C=spd(C_1,C_2)$ (right), the same edge is oriented from 5 to 2 in the $\alpha$-sum of C. As a consequence, in this case, we have $s_\alpha (C_1)=s_\alpha (C_2)=0$ and $s_\alpha (C)=2\ne 0$.

Fig. 2.

A graph G with $n=5$ vertices, such that $B_c(G)=2$, in which the labels of an optimal cb-labeling $\varphi$ are also the vertices identifiers. Edges in $C_1$ (left), $C_2$ (middle), and $C=spd(C_1,C_2)$ (right) are arbitrarily oriented to compute their respective $\alpha$-sum. It can be seen that, in any case, $s_\alpha (C_1)=s_\alpha (C_2)=0$, while $s_\alpha (C)=2$.

The example shown in Fig. 2 shows that $s_\alpha$ is not necessarily conserved by symmetric difference. However, in the following lemma, which is a stronger version of Lemma 3.2 from [4], we are able to show that all cycles have a 0 $\alpha$-sum under certain conditions.

Lemma 7

Let G be a graph, and $\varphi$ an optimal cb-labeling of G. If the set of cycles of G of length at most $\ell < \frac{n}{B_c(G)}$ contains a cycle basis, then for any cycle C of G, $s_\alpha (C)=0$.

Proof

Let $\varphi$ be an optimal cb-labeling of G. Assume, by contradiction, that there is a cycle C of G such that $s_\alpha (C)\ne 0$. Remove from G all edges that have a non-zero $\alpha _\varphi$, and let $S_1,S_2,..,S_p$ denote the connected components of the resulting graph. For each connected component $S_i$, $1\le i\le p$ and any subgraph $G'=(V',E')$ of G, we define the following function $\gamma _i(G')$: $\gamma _i(G')=\sum _{e\in E(G')} \gamma _i(e)$, where for any edge $uv\in E(G')$, $\gamma _i(uv)=1$ if $\alpha (u,v)\ne 0$ and at least one vertex (say x) among u, v satisfies (i) $\varphi (x)>\frac{n}{2}$ and (ii) $x\in V(S_i)$ ; and $\gamma _i(uv)=0$ otherwise.

One of the interests of $\gamma _i$ is that, unlike $\alpha _\varphi$, this funtion is symmetric: any edge uv will contribute the same way to $\gamma _i$, whether it is considered from u to v or from v to u. We will now prove Lemma 7 through a series of three claims.

Claim 1

Let $1\le i\le p$, and let $G_1$ and $G_2$ be two subgraphs of G such that $\gamma _i(G_1)$ and $\gamma _i(G_2)$ are even. Then, $G'=psd(G_1,G_2)$ is such that $\gamma _i(G')$ is even.

Proof

(of Claim 1). Take any $1\le i\le p$, and let $G_1$ and $G_2$ be two subgraphs of G such that both $\gamma _i(G_1)$ and $\gamma _i(G_2)$ are even. Then $\gamma _i(psd(G_1,G_2))=\gamma _i(G_1)+\gamma _i(G_2)-2\cdot \sum _{e\in E(G_1)\cap E(G_2)} \gamma _i(e)$, since all edges e present in both $G_1$ and $G_2$ are removed from $psd(G_1,G_2)$. Since all numbers in the above equation are even, $\gamma _i(sd(G_1,G_2))$ is also even.    $\square$

Claim 2

Any cycle $C'$ of G whose length $\ell$ satisfies $\ell < \frac{n}{B_c(G)}$ is such that $\gamma _i(C')$ is even for any $1\le i\le p$.

Proof

(of Claim 2). Observe a cycle $C'=(x_0,x_1,...,x_\ell )$ (with $x_0=x_\ell$) of G, of length $\ell < \frac{n}{B_c(G)}$, and consider the set $\mathcal {L}$ of labels that are used to label $V(C')$. We claim that $\mathcal {L}$ belongs to a (cyclic) interval I of cyclic length strictly less than $\frac{n}{2}$. In order to show this, let u (resp. v) be the vertex of $C'$ whose label is minimum (resp. maximum), and let $\varphi _{\min }=\varphi (u)$ (resp. $\varphi _{\max }=\varphi (v)$). Now let us consider the set $\mathcal {L}$ of labels that are used to label $V(C')$. There are three possible cases for $\mathcal {L}$: first, suppose $\mathcal {L}\subseteq [\varphi _{\min };\varphi _{\max }]$. Then, $I=[\varphi _{\min };\varphi _{\max }]$, and I is of length strictly less than $\frac{n}{2}$ by definition of the cyclic bandwidth and since $B_c(G) < \frac{n}{\ell }$. Second, suppose $\mathcal {L}\subseteq [1;\varphi _{\min }]\cup [\varphi _{\max };n]$. For the same reasons as in the previous case, we conclude that the interval $I=[1;\varphi _{\min }]\cup [\varphi _{\max };n]$ is of cyclic length strictly less than $\frac{n}{2}$. Third, suppose we are not in one of the two above cases, and let us show that this case cannot happen: indeed, this means that at least one vertex $x\ne u,v$ (resp. $y\ne u,v$) of $V(C')$ satisfies $\varphi (x)\in [1;\varphi _{\min }[\; \cup \; ]\varphi _{\max };n]$ (resp. $\varphi (y)\in \; ]\varphi _{\min };\varphi _{\max }[$. We will say that x (resp. y) has a small (resp. high) label. Now let $P_x$ denote the path from u to v, that contains x, and that follows the edges of $C'$. Let $S_x$ be the sum of $|\varphi (a)-\varphi (b)|_n$ over all edges ab in $P_x$. Then, we know that $S_x\ge \varphi _{\max }-\varphi _{\min }$. Now consider the path $P_y$ going from u to v that contains y, and that follows the edges of $C'$. Let $S_y$ be the sum of $|\varphi (c)-\varphi (d)|_n$ over all edges cd in $P_y$. Then we know that $S_y\ge n-\varphi _{\max }+\varphi _{\min }$. Hence, $S_x+S_y\ge n$. We will now show that, since we supposed $\ell < \frac{n}{B_c(G)}$, this cannot happen. Indeed, we have $S_x+S_y= \sum _{i=0}^{\ell -1} |\varphi (x_{i+1})-\varphi (x_i)|_n\le \ell \cdot B_c(G)$, because for any two neighbors $x_{i+1}$ and $x_i$ in $C'$ we have $|\varphi (x_{i+1})-\varphi (x_i)|_n\le B_c(G)$, by definition of $B_c(G)$. Moreover, we know by hypothesis that $\ell \cdot B_c(G)<n$, thus we conclude that $S_x+S_y<n$, a contradiction.

We just proved that $\mathcal {L}$ belongs to a (cyclic) interval I of cyclic length strictly less than $\frac{n}{2}$. Let us now observe interval I. There are two cases: first, if either 1 or n is not in I, then all edges uv of $C'$ satisfy $\alpha _\varphi (u,v)=0$, by definition of $\alpha _\varphi$ and because $B_c(G)\le \frac{n}{2}$ for any graph G. Thus, every edge of $C'$ contributes to zero in $\gamma _i(C')$, and consequently $\gamma _i(C')=0$ for any $1\le i\le p$.

Second, if both 1 and n are present in I, take any integer $1\le i\le p$ and partition the vertices of $C'$ in two sets: the first set $V_1$ contains every vertex $u\in V(C')$ such that $\varphi (u)>\frac{n}{2}$ and $u\in V(S_i)$ ; the second set is $V_2=V(C')-V_1$.

Let uv be an edge of $C'$. We will say that uv is a crossing edge if $u\in V_1$ and $v\in V_2$, or vice-versa – this term refers to the fact that, as we will prove it, a crossing edge uv necessarily satisfies $\alpha (u,v)\ne 0$, and thus, crosses the dashed vertical as in Fig. 1. Take any edge uv in $C'$. By definition, $\gamma _i(uv)\in \{0,1\}$. Our goal here is to show that $\gamma _i(uv)=1$ iff uv is a crossing edge.

($\Leftarrow$) Suppose uv is a crossing edge, and suppose wlog that $u\in V_1$ and $v\in V_2$. In that case, $\varphi (v)<\frac{n}{2}$. Otherwise, we would have $\alpha _\varphi (u,v)=0$ (by definition of $\alpha _\varphi$, because the labels of u and v are separated by less than $B_c(G)$), which implies that both vertices u and v belong to $S_i$, since $u\in V(S_i)$. But in that case v would belong to $V_1$, since $v\in V(S_i)$ and $\varphi (v)>\frac{n}{2}$. This is a contradiction since v cannot simultaneously belong to $V_1$ and $V_2$. Thus, every crossing edge uv with $u\in V_1$ and $v\in V_2$ is such that $\varphi (v)<\frac{n}{2}$, and consequently $\alpha _\varphi (u,v)\ne 0$. This implies that for any such edge uv, $\gamma _i(uv)=1$.

($\Rightarrow$) Now suppose $\gamma _i(uv)=1$, which implies $\alpha _\varphi (u,v)\ne 0$. Thus, there are two cases: $\alpha _\varphi (u,v)>0$ or $\alpha _\varphi (u,v)<0$. First, if $\alpha _\varphi (u,v)>0$, and since $\gamma _i(uv)=1$, then $u\in V(S_i)$ by definition. Moreover, $\alpha _\varphi (u,v)>0$ implies (by definition) $\varphi (u)\ge \varphi (v)+n-B_c(G,\varphi )$. Since $B_c(G,\varphi )\le \frac{n}{2}$ for any graph G and any labeling $\varphi$, and since $\varphi (v)\ge 1$, we conclude that $\varphi (u)>\frac{n}{2}$. We then know that $u\in V_1$ by definition. Moreover, $v\not \in V_1$, otherwise $uv\in E(S_i)$, a contradiction to the fact that all edges in $E(S_i)$ have a zero $\alpha _\varphi$. Thus, we conclude that $v\in V_2$, and that uv is a crossing edge. Now if $\alpha _\varphi (u,v)<0$, by a symmetrical argument as above, we conclude that $v\in V_1$ and $u\in V_2$, i.e., uv is a crossing edge as well.

We thus know that each edge $uv\in E(C')$ contributes to 1 to $\gamma _i$ iff uv is a crossing edge. This allows us to prove the claim: if we follow the edges of $C'$ to compute $\gamma _i(C')$, the number of crossing edges encountered is necessarily even, since $C'$ starts and ends in the same vertex. Since only a crossing edge increases $\gamma _i$ (by exactly 1), we conclude that $\gamma _i(C')$ is even.    $\square$

Claim 3

There exists an integer $1\le j\le p$ and a cycle $C'$ of G such that $\gamma _j(C')=1$.

Proof

(of Claim 3). Recall that we suppose there exists a cycle C in G such that $s_\alpha (C)\ne 0$. For each $1\le i\le p$, let $\varSigma _i$ be the sum of the $\alpha _\varphi (u,v)$ for each edge uv of C that has an extremity in $S_i$, counting uv twice in $\varSigma _i$ if both $u,v\in V(S_i)$. The sum of the $\varSigma _i$s over every $1\le i\le p$ is thus equal to $2s_\alpha (C)$.

Since we supposed $s_\alpha (C)\ne 0$, we know there exists at least one j, $1\le j\le p$, such that $\varSigma _j\ne 0$. Thus, there exists at least one edge $uv\in E(C)$ such that (i) at least one of $u,v\in V(S_j)$, and (ii) $\alpha _\varphi (u,v)\ne 0$.

Now let us look at every edge along C (following the natural order of the cycle), and let us observe each pair (uv, wx) of edges (with possibly $uv=wx$) satisfying the following: (i) $\alpha _\varphi (u,v)\ne 0$ and $u\in V(S_j)$ and (ii) $\alpha _\varphi (w,x)\ne 0$ and $x\in V(S_j)$. Because $\varSigma _j\ne 0$, such a pair (again with possibly $uv=wx$) must exist. Moreover, among such pairs, and since $\varSigma _j\ne 0$, there necessarily exists a pair, say (ab, cd), such that $\alpha _\varphi (a,b)=\alpha _\varphi (c,d)$.

There are now two cases to consider. First, if $ab=cd$, then we construct the cycle $C_1$ containing edge ab and edges of a path $P_{a,b}$ joining a to b in $S_j$ (we know there exists such a path, since $a,b\in V(S_j)$, and $S_j$ is connected by definition). By definition also, $P_{a,b}$ only contains zero $\alpha _\varphi$ edges. Thus $\gamma _j(C_1)=1$, since only edge ab contributes to 1 to $\gamma _j(C_1)$ – all other edges of $C_1$ contribute to 0.

Second, if $ab\ne cd$, take the path $P=ab\ldots cd$ in C that connects a to d through ab and cd. Path P has no internal vertex in $S_j$ by construction. Consider a second path $P'=a\ldots d$ connecting a to d within $S_j$ (again, $P'$ exists since $a,d\in V(S_j)$ by definition, and since $S_j$ is connected). Note that P and $P'$ only intersect in a and d. Then, we can construct cycle $C_2$, which is the concatenation of P and $P'$. What is important to observe is that only one of the two edges ab or cd will contribute to 1 in the computation of $\gamma _j(C_2)$ – the other will contribute to 0. Moreover, all other edges from P contribute to 0 to $\gamma _j(C_2)$ (because none contains a vertex of $S_j$), and the same conclusion is reached with any edge of $P'$: by definition, each such edge belongs to $S_j$, and thus is a zero $\alpha _\varphi$ edge.    $\square$

We are now ready to prove Lemma 7. Suppose the set of cycles of G of length at most $\ell <\frac{n}{B_c(G)}$ contains a cycle basis $\mathcal {C}$. Observe an optimal cb-labeling $\varphi$ of G, and suppose by contradiction that there exists a cycle C in G such that $\alpha _\varphi (G)\ne 0$. By Claim 3, we know that there exists a cycle $C'$ and an integer j such that $\gamma _j(C')=1$. Besides, we know by definition that $C'$ can be obtained by symmetric difference of elements of $\mathcal {C}$.

However, Claims 2 and 1 respectively yield that any cycle in $\mathcal {C}$ has even $\gamma _i$ and thus that any symmetric difference of elements of $\mathcal {C}$ also has even $\gamma _i$. We thus get the desired contradiction, which in turn proves Lemma 7.    $\square$

Note that Lemma 7 remains correct if $\varphi$ is not an optimal labeling (but in that case, $B_c(G)$ should be replaced by $B_c(G,\varphi )$ in the lemma’s statement).

The next lemma provides a sufficient condition yielding $B(G)=B_c(G)$, improved from [4]. It is the last step towards proving Theorem 9, and needs Lemma 7 to be proved.

Lemma 8

If the set of cycles of G of length at most $\ell < \frac{n}{B_c(G)}$ contains a cycle basis, then $B_c(G)=B(G)$.

Proof

Suppose G satisfies the conditions of the lemma, and let $\varphi$ be a cb-labeling of G. We will show in the following that Algorithm 1 below computes a bm-labeling $\varphi '$ of G satisfying $B(G,\varphi ')\le B_c(G,\varphi )$. If $\varphi$ is optimal, then $B_c(G,\varphi )=B_c(G)$, and consequently $B(G,\varphi ')=B_c(G)=B(G)$ (i.e., $\varphi '$ is an optimal bm-labeling) since $B(G)\ge B_c(G)$ for any graph G.

We need Claims 4 and 5 to show that $B(G,\varphi ')\le B_c(G,\varphi )$.

Claim 4

For any adjacent vertices u and v, $\beta (v)=\beta (u)+\alpha _\varphi (u,v)$.

Proof

(of Claim 4). First suppose v has been discovered by u during the Depth-First Search (DFS) in Algorithm 1: then Line 6 of Algorithm 1 yields $\beta (v)=\beta (u)+\alpha _\varphi (u,v)$. Symmetrically, the result is proved if u has been discovered by v during the DFS, since $\alpha _\varphi (u,v)=-\alpha _\varphi (v,u)$ for any labeling $\varphi$ and any edge $uv\in E(G)$. Now suppose none of u and v have discovered the other during the DFS. Since u and v are in the same connected component, by property of DFS, there exists a vertex s such that $\beta (s)=0$ and two paths $P_u=u_0u_1u_2...u_p$ (with $u_0=s$ and $u_p=u$) and $P_v=v_0v_1v_2...v_q$ (with $v_0=s$ and $v_q=v$), such that $\beta (u_{i+1})=\beta (u_i)+\alpha _\varphi (u_i,u_{i+1})$ for any $0\le i\le p-1$ and $\beta (v_{i+1})=\beta (v_i)+\alpha _\varphi (v_i,v_{i+1})$ for any $0\le i\le q-1$. Therefore, we have $\beta (u)=\sum _{i=0}^{p-1}\alpha _\varphi (u_i,u_{i+1})$ and $\beta (v)=\sum _{i=0}^{q-1}\alpha _\varphi (v_i,v_{i+1})$.

Suppose first that $P_u$ and $P_v$ only share vertex s. In that case, we obtain a cycle $C_{uv}$ by concatenating paths $P_u,P_v$ and edge uv. Since we are in the conditions of Lemma 7, we conclude that $s_\alpha (C_{uv})=0$. Observe that $s_\alpha (C_{uv})= S_{P_u}+\alpha _\varphi (u,v)+S_{P_v}$, where $S_{P_u}=\sum _{i=0}^{p-1}\alpha _\varphi (u_i,u_{i+1})=\beta (u)$ and $S_{P_v}=\sum _{i=0}^{q-1}\alpha _\varphi (v_{i+1},v_i))=-\sum _{i=0}^{q-1}\alpha _\varphi (v_i,v_{i+1})=-\beta (v)$. Hence we conclude that $\beta (u)+\alpha _\varphi (u,v)-\beta (v)=0$, which is the desired result.

If $P_u$ and $P_v$ share more than vertex s, consider the common vertex between both paths having the largest index $r>0$ in $P_u=u_0u_1\ldots u_p$, and let t be such that $u_r=v_t$. Thus, we can write $P_u=P_r\cdot P$ (where $P_r=u_0u_1\ldots u_r$) and $P_v=P_t\cdot P'$ (where $P_t=v_0v_1\ldots v_t$), and in that case $S_{P_u}=S_{P_r}+S$ and $S_{P_v}=S_{P_t}+S'$, where $S_{P_r}=\sum _{i=0}^{r-1}\alpha _\varphi (u_i,u_{i+1})$, $S=\sum _{i=r}^{p-1}\alpha _\varphi (u_i,u_{i+1})$, $S_{P_t}=\sum _{i=0}^{t-1}\alpha _\varphi (v_i,v_{i+1})$ and $S'=\sum _{i=t}^{q-1}\alpha _\varphi (v_i,v_{i+1})$. Again, if we concatenate P, $P'$ and uv, we get a cycle $C_{rt}$ and by Lemma 7 we have $s_\alpha (C_{rt})=0$. Thus, it remains to show that $S_{P_r}-S_{P_t}=0$ to conclude. This is done by induction on r. When $r=0$, we are in the case where $P_u$ and $P_v$ only share vertex s, which has already been discussed. When $r=1$, $P_r=u_0u_1=su_1$ is limited to one edge. If $t=1$, then $v_1=u_1$ and $P_t=P_r=su_1$ and by antisymmetry of $\alpha _\varphi$ we have $S_{P_r}-S_{P_t}=\alpha _\varphi (s,u_1)+\alpha _\varphi (u_1,s)=0$. If $t>1$, then concatenating edge $P_r$ and path $P_t$ yields a cycle $C'$, for which we know by Lemma 7 again that $s_\alpha (C')=S_{P_r}-S_{P_t}=0$. Now if $r>1$, apply induction hypothesis to $r'$, where $r'$ is the largest index (with $r'<r$) of a vertex of $P_u$ also belonging to $P_v$. Let $t'$ be the corresponding index in $P_v$. Then, $P_u=P_{r'}\cdot P_{r'r}\cdot P$ and $P_u=P_{t'}\cdot P_{t't}\cdot P'$, where $P_{r'r}$ (resp. $P_{t't}$) is a path from $r'$ to r (resp. from $t'$ to t). By induction hypothesis, $S_{P_{r'}}-S_{P_{t'}}=0$. Moreover, concatenating $P_{r'r}$ and $P_{t't}$ yields a cycle $C''$, which satisfies, by Lemma 7, $s_\alpha (C'')=0$. Since $s_\alpha (C'')=S_{P_{r'r}}-S_{P_{t't}}$, we obtain altogether that $(S_{P_{r'}}+S_{P_{r'r}})-(S_{P_{t'}}+S_{P_{t't}})=0$. But $S_{P_{r'}}+S_{P_{r'r}}=S_{P_r}$ and $S_{P_{t'}}+S_{P_{t't}}=S_{P_t}$, hence we conclude $S_{P_r}-S_{P_t}=0$, and the proof by induction holds. Altogether, we have $S_{P_r}-S_{P_t}=0$ in all cases. This allows us to conclude that $\beta (v)=\beta (u)+\alpha _\varphi (u,v)$.    $\square$

Claim 5

For any two adjacent vertices x and y in G, $|\varphi ^*(y)-\varphi ^*(x)|=|\varphi (y)-\varphi (x)|_n$.

Proof

(of Claim 5). If $\alpha _\varphi (x,y)=0$, then $\beta (y)=\beta (x)$ by Claim 4. Thus, we have $|\varphi ^*(y)-\varphi ^*(x)|=|\varphi (y)-\varphi (x)|$. However, by definition of $\alpha _\varphi$, we know that $|\varphi (y)-\varphi (x)|\le B_c(G,\varphi )$ and thus $|\varphi (y)-\varphi (x)|_n=|\varphi (y)-\varphi (x)|=|\varphi ^*(y)-\varphi ^*(x)|$. Suppose now $\alpha _\varphi (x,y)=1$. Then, by Claim 4 again, $\beta (y)=\beta (x)+1$, and consequently $|\varphi ^*(y)-\varphi ^*(x)|=|\varphi (y)-\varphi (x)+n|=n-(\varphi (x)-\varphi (y))$ (because $\alpha _\varphi (x,y)=1$ implies $\varphi (x)>\varphi (y)$). We then conclude that $|\varphi ^*(y)-\varphi ^*(x)|=|\varphi (y)-\varphi (x)|_n$. Finally, if $\alpha _\varphi (x,y)=-1$, by a symmetrical argument as above, we get that $|\varphi ^*(y)-\varphi ^*(x)|=|\varphi (y)-\varphi (x)-n|=n-(\varphi (y)-\varphi (x))$ (because $\alpha _\varphi (x,y)=-1$ implies $\varphi (x)<\varphi (y)$). Finally, $|\varphi ^*(y)-\varphi ^*(x)|=|\varphi (y)-\varphi (x)|_n$.

   $\square$

We are now ready to finish proof of Lemma 8. First, note that $\varphi ^*$ is injective, since for any vertex v, $\varphi ^*(v)$ is congruent to $\varphi (v)$ modulo n. Moreover, since $\varphi ^*$ is injective, $\varphi '$ is also injective. As $|V|=n$, $\varphi '$ is a bijection from V to [n]. Moreover, $|\varphi '(y)-\varphi '(x)|$ is equal to the number of vertices v for which $\varphi ^*(v)$ lies between $\varphi ^*(y)$ (included) and $\varphi ^*(x)$ (excluded). Since $\varphi ^*$ is injective, this number is less than or equal to $|\varphi ^*(y)-\varphi ^*(x)|$, so we have $|\varphi '(y)-\varphi '(x)|\le |\varphi ^*(y)-\varphi ^*(x)|$. Since we know by Claim 5 that $|\varphi ^*(y)-\varphi ^*(x)|=|\varphi (y)-\varphi (x)|_n$, we conclude that $\varphi '$ is a bm-labeling satisfying $B(G,\varphi ')\le B_c(G,\varphi )$. In particular, if $\varphi$ is an optimal cb-labeling, then $B_c(G,\varphi )=B_c(G)$ and thus $B(G,\varphi ')\le B_c(G)$. But since for any graph G, $B(G)\ge B_c(G)$, we conclude that $B(G,\varphi ')= B_c(G)$. Consequently $\varphi '$ is an optimal bm-labeling, and $B(G)=B_c(G)$.    $\square$

Our main result of the section is now stated.

Theorem 9

Let G be a graph and let $\ell$ be the length of the longest cycle of a cycle basis of G. Then, we have $B_c(G)\ge \min \{B(G),\left\lceil \frac{n}{\ell }\right\rceil \}$. In particular, if $B(G)\le \left\lceil \frac{n}{\ell }\right\rceil$, then $B(G)=B_c(G)$.

Proof

Suppose first $B_c(G)\ge \left\lceil \frac{n}{\ell }\right\rceil$. Since $B(G)\ge B_c(G)$ for any graph, we have $B(G)\ge \left\lceil \frac{n}{\ell }\right\rceil$, which proves the result. Now suppose $B_c(G)< \left\lceil \frac{n}{\ell }\right\rceil$. In that case we have $B_c(G)< \frac{n}{\ell }$, since $B_c(G)$ is an integer, and by Lemma 8 we conclude that $B(G)=B_c(G)$.

4 Applying Our Results on 28 Harwell-Boeing Instances

We now illustrate how the results we obtained in Sects. 2 and 3 improve previous knowledge, by applying them on instances taken from the Harwell-Boeing sparse matrix collection. This benchmark contains a large number of matrices (that we interpret as graphs here) derived from several industrial applications. This collection has often been used as a benchmark for both the Bandwidth Minimization and Cyclic Bandwidth problems, see e.g. [10,11,12,13,14]. Before going further, we note that all lower bound results provided in previous sections can be computed in polynomial time. Hence, computational performances are not provided here, as they do not play a major role.

Table 1. Summary of results applied to a set of 28 instances from the Harwell-Boeing repository, sorted by increasing $n=|V(G)|$. The rightmost column presents the best lower bound obtained by our results (i.e., the maximum value obtained by Theorems 1, 3, and 9). In the leftmost and rightmost column, asterisks indicate optimality, while bold values in the rightmost column indicate a strict improvement compared to previous knowledge. Note that the “Best Known Upper Bound” for bcspwr03 we report here is the only result not imported from [13] (where the reported bound is 10). Indeed, we know by [11] that $B(G)\le 9$ for that instance; since $B_c(G)\le B(G)$ for any graph G, we get a(n optimal) upper bound of 9 for bcspwr03.

We took a set of 28 Harwell-Boeing instances, that have recently been specifically used for the Cyclic Bandwidth problem [12,13,14]. Our results are summarized in Table 1. The three leftmost columns describe the instance: respectively its usual name, its number n of vertices, and m of edges. The next column (“Best Know Upper Bounds”) provides the best upper bounds results concerning $B_c$, which are taken from the recent paper by Ren et al. [13]. Optimal values for $B_c(G)$ are marked with an asterisk.

The five remaining columns are computations and informations derived from the present work: in a nutshell, column “Lower Bound Density” contains the best result obtained by Theorems 1 and 3 (each theorem being applied for all possible values of i and any vertex v in the case of Theorem 1, and for all possible values of i and any edge uv in the case of Theorem 3), while column “Lower Bound Cycle Basis” contains the best results obtained by Theorem 9. Note that for computing the values in this column, we need to determine the length $\ell$ of the longest cycle in a cycle basis for G (column “$\ell$”) ; then, based on $\ell$ and on known upper bounds on B(G) [11], we can (most of the time, see column “$B(G)=B_c(G)$?”) determine whether $B(G)=B_c(G)$. If $B(G)=B_c(G)$, then we can invoke the best known lower bounds from B(G) taken from [10]. If not, we apply Theorem 9 and take the minimum between $\frac{n}{\ell }$ and (the best lower bound on) B(G). Finally, the righmost column, “Lower Bound from our results”, simply takes the maximum value between the one in column “Lower Bound Density” (Theorems 1 and 3) and the one in column “Lower Bound Cycle Basis” (Theorem 9).

In the rightmost column of Table 1, which summarizes our results, values in bold show a strict improvement from previous lower bound results (based on the lower bounds for $B_c(G)$ taken from [13]), while an asterisk shows that the lower bound we obtain is actually optimal.

We first note that, among the 28 instances, our density lower bound is strictly better than our cycle basis lower bound 10 times, while the opposite happens 11 times (and thus it is a draw for the 7 remaining instances). This shows that both types of lower bounds are useful for improvement.

We also observe that Ren et al. [13] have determined the optimal value for $B_c(G)$ for 9 instances (the 7 first together with curtis54 and bscpwr03), hence our results cannot strictly improve them. It should be noted however, that for 8 out of these 9 instances, our lower bounds results are actually optimal (as shown by the asterisks in the rightmost column). Our results also show that, among the 19 remaining instances, we have been able to determine the optimal values for $B_c(G)$ for 6 of them, since our new lower bounds appear to be matching the upper bounds for $B_c$ provided by [13]. This clearly shows the interest of our work in aiming at increasing the lower bounds.

Concerning the 13 remaining instances, our results have drastically reduced the gap between lower and upper bounds for $B_c$, which now ranges from 1 (instances can445 and nos6) to 12 (instance dwt_503), with an average gap of 5.54. Previously, based on the results presented in [13], the gap between lower and upper bounds ranged between 8 and 40, with an average of 24.31. Over the 28 studied instances, there are only two cases for which our results have neither reached the optimal value for $B_c$ nor strictly improved previous lower bounds – namely instances ibm32 and can_715.

5 Conclusion and Open Questions

In this paper, we have studied the Cyclic Bandwidth problem, and have particularly focused on determining new lower bounds for $B_c(G)$ for any graph G. We have, on the way, provided a relabeling algorithm (Algorithm 1) of a graph G that, under specific conditions, computes a labeling $\varphi '$ for the Bandwidth Minimization problem, starting from a labeling $\varphi$ for Cyclic Bandwidth such that $B(G,\varphi ')\le B_c(G,\varphi )$. We have applied our results to a benchmark of 28 Harwell-Boeing instances already used in [12,13,14], and showed how our results greatly improve the best current knowledge.

The results we provide here may open the door to further improvements. In particular, it would be worth investigating whether they could help determining $B_c(G)$ for new families of graphs. They could also, in a more general setting, help better characterize properties of graphs satisfying $B_c(G)=B(G)$.

Concerning the benchmark that we used, note that among the 28 Harwell-Boeing instances from Table 1, we have not been able to determine whether $B_c(G)=B(G)$ for 4 instances, and investigating that question could be of interest. Finally, we observe that there exists graphs for which Algorithm 1, starting from a suboptimal labeling $\varphi$ for Cyclic Bandwidth, is able to compute an optimal labeling $\varphi '$ for both Bandwidth Minimization and Cyclic Bandwidth. Hence, it would be interesting to apply Algorithm 1 on the instances from Table 1 for which conditions of Lemma 8 are fulfilled, in order to determine whether this technique helps improving the knowledge on B and/or $B_c$.