## 3 Polynomial Time Algorithms for the Bandwidth Problem
### Linear Time Algorithm for a Threshold Graph  
We first show a linear time algorithm for computing \(\mathsf{bw}(G)\) of a connected threshold graph \(G\). For a threshold graph \(G=(V,E)\), there exist nonnegative weights \(w(v)\) for \(v\in V\) and \(t\) such that \(\{u,v\}\in E\) if and only if \(w(u)+w(v)\geq t\). We assume that a threshold graph is given in the standard adjacency list manner. That is, each vertex has its own neighbor list and it knows its degree and weight. We assume that \(G\) is connected and \(V\) is already ordered as \(\{v_{1},v_{2},\ldots,v_{n}\}\) with \(w(v_{i})\leq w(v_{i+1})\) for \(1\leq i<n\) (this sort can be done in \(O(n)\) time by a standard bucket sort (Serge, Section 5.2.5) according to the degrees of vertices; ties may occur by twins, and are broken in any way). We can find \(\ell\) such that \(w(v_{\ell-1})+w(v_{\ell})<t\) and \(w(v_{\ell})+w(v_{\ell+1})\geq t\) in \(O(n)\) time. Then \(G\) has the following interval representation \(\mathcal{I}(G)\):  
* For \(1\leq i\leq\ell\), \(v_{i}\) corresponds to the point \(i\), that is, \(I_{v_{i}}=[i,i]\). * For \(\ell<i\leq n\), \(v_{i}\) corresponds to the interval \([j,\ell]\), where \(j\) is the minimum index with \(w(v_{i})+w(v_{j})\geq t\). For example, Figure 1(a) is a threshold graph; each number in a circle is its weight, and threshold value is 5. We have \(\ell=5\) and its interval representation is given in Figure 1(b). Figure 1: (**a**) Threshold graph and (**b**) its interval representation. **Theorem 6**: _We assume that a connected threshold graph \(G=(V,E)\) is given in the interval representation \(\mathcal{I}(G)\) stated above. Then we can compute \(\mathsf{bw}(G)\) in \(O(n)\) time and space._  
Proof. We first observe that \(L(I_{v_{i}})<L(I_{v_{i+1}})\) and \(R(I_{v_{i}})<R(I_{v_{i+1}})\) for each \(v_{i}\) with \(1\leq i<\ell\), and \(L(I_{v_{i}})\geq L(I_{v_{i+1}})\) and \(R(I_{v_{i}})=R(I_{v_{i+1}})=\ell\) for each \(i\) with \(\ell<i<n\). That is, \(G\) consists of two proper interval graphs induced by \(\{v_{1},v_{2},\ldots,v_{\ell}\}\) and \(\{v_{\ell},v_{\ell+1},\ldots,v_{n}\}\) (note that \(v_{\ell}\) is shared). Their proper interval representations also appear in \(\mathcal{I}(G)\). Hence, by Lemma 5, there exists an optimal layout \(\pi\) of \(V=\{v_{1},\ldots,v_{n}\}\) such that \(\pi(v_{1})<\pi(v_{2})<\cdots<\pi(v_{\ell})\) and \(\pi(v_{\ell})>\pi(v_{\ell+1})>\pi(v_{\ell+2})>\cdots>\pi(v_{n})\). Thus we can obtain an optimal layout by merging two sequences of vertices. To obtain an optimal layout, by Observation 4, we construct a minimum completion of \(G\) from two sequences. The longest interval is given by \(v_{n}\); since \(G\) is connected, \([L(I_{v_{n}}),R(I_{v_{n}})]=[1,\ell]\). Hence, we extend all intervals (except \(I_{v_{n}}\)) to length \(\ell-1\) and construct a minimum completion. We denote the extended interval \(I_{v_{i}}\) by \(I^{\prime}_{v_{i}}\). That is, the length of \(I^{\prime}_{v_{i}}=\ell-1\) for all \(i\) with \(1\leq i\leq n\). The extension is illustrated in Figure 2. The extension of intervals \(I_{v_{i}}\) for \(i>\ell\) is straightforward; just extend them to the right, which does not increase the size of a maximum clique. Thus we focus on the points \(I_{v_{i}}=[i,i]\) with \(i\leq\ell\), which are extended to \(I^{\prime}_{v_{i}}\) with length \(\ell-1\). If \(I^{\prime}_{v_{i}}\) does not contain the point 1, \(I^{\prime}_{v_{i}}\) has to contain the point \(\ell\) since it has to have length \(\ell-1\). On the other hand, once \(I^{\prime}_{v_{i}}\) contains the point \(\ell\), we can set \(I^{\prime}_{v_{i}}=[i..\ell+i-1]\) without loss of generality. Otherwise, the size of a maximum clique at the left side of the point \(i\) may increase. Similarly, once \(I^{\prime}_{v_{i}}\) does not contain the point \(\ell\), we can set \(I^{\prime}_{v_{i}}=[-\ell+i+1..i]\) without loss of generality. That is, we can assume that \(L(I^{\prime}_{v_{i}})=i\) or \(R(I^{\prime}_{v_{i}})=i\) for each \(1\leq i\leq\ell\).