## 3 Polynomial Time Algorithms for the Bandwidth Problem
### Linear Time Algorithm for a Threshold Graph
If two intervals \(I^{\prime}_{v_{i}}\) and \(I^{\prime}_{v_{j}}\) satisfy \(i<j\leq\ell\), \(L(I^{\prime}_{v_{i}})=i\), and \(R(I^{\prime}_{v_{j}})=j\), we can make \(R(I^{\prime}_{v_{i}})=i\), and \(L(I^{\prime}_{v_{j}})=j\) without increasing the size of a maximum clique. Specifically, we can take \(R(I^{\prime}_{v_{1}})=1\) and \(L(I^{\prime}_{v_{\ell}})=\ell\). From the above observation, a minimum completion is given by the following proper interval representation of \(n\) intervals of length \(\ell-1\) for some \(m\) with \(1\leq m<\ell\): (0) for each \(i>\ell\), \(L[I_{v_{i}}]=j\), where \(j\) is the minimum index with \(w(v_{i})+w(v_{j})\geq t\); (1) for each \(1\leq i\leq m\), \(R[I_{v_{i}}]=i\), and (2) for each \(m<i\leq\ell\), \(L[I_{v_{i}}]=i\) (Figure 2). Thus, to construct a minimum completion, we search the index \(m\) that minimizes a maximum clique in the proper interval graph represented by above proper interval representation determined by \(m\). In the minimum completion, there are \(\ell\) distinct cliques \(C_{i}=N[i]\), one induced at each point \(i\) with \(1\leq i\leq\ell\). Now we consider a maximum clique of the corresponding proper interval graph for a fixed \(m\in[1..\ell]\). Figure 2: Construction of a minimum completion. At points in \([m+1..\ell]\), it is easy to see that \(N[m+1]\subseteq\cdots\subseteq N[\ell]\) and hence the point \(\ell\) induces maximum clique of size \((n-(\ell+1)+1)+(\ell-(m+1)+1)=(n-m)\). We next consider each point \(i\) in \([1..m]\). At the point \(i\), \(N[i]\) induces a clique that consists of \(\{v_{i},v_{i+1},\ldots,v_{m}\}\) and \(\{v_{j},v_{j+1},\ldots,v_{n}\}\), where \(j\) is the minimum index with \(w(v_{i})+w(v_{j})\geq t\). Hence we have a clique of size \((m-i+1)+(n-j+1)\) at point \(i\). Thus we have to find \(i\) in \([1..m]\) that gives a maximum one. Therefore, for a fixed \(m\), we compute these two candidates for a maximum clique from \([1..m]\) and \([m+1..\ell]\), compare them, and obtain a maximum one. For every \(m\), we have to find a minimum one of the maximum cliques, whose size gives \(\text{bw}(G)+1\). Thus we can compute \(\text{bw}(G)\) by Algorithm 2. ```
Input : Threshold graph \(G=(V,E)\) with \(w(v_{1})\leq w(v_{2})\leq\cdots\leq w(v_{n})\) and \(t\) Output : \(\text{bw}(G)\)  let \(\ell\) be the minimum index with \(w(v_{\ell})+w(v_{\ell+1})\geq t\);  set \(bw:=\infty\); for\(m=1,2,\ldots,\ell-1\)do  set \(lc:=0\); // size of a maximum clique at points in \([1..m]\) for\(i=1,2,\ldots,m\)do  let \(j\) be the minimum index with \(w(v_{i})+w(v_{j})\geq t\); if\(lc<(m-i+1)+(n-j+1)\)then set \(lc:=(m-i+1)+(n-j+1)\); if\(\max\{lc,n-m\}<bw\)then\(bw:=\max\{lc,n-m\}\); return(\(bw-1\)). ```  
**Algorithm 2**Bandwidth of a threshold graph  
The correctness of Algorithm 2 follows from Observation 4, Lemma 5 and the above discussions. Algorithm 2 runs in \(O(n^{2})\) time and \(O(n)\) space by a straightforward implementation. However, careful implementation achieves \(O(n)\) time and space as follows. When the algorithm updates \(m\) in step 3, the proper interval representation does not change except for one vertex \(v_{m+1}\). We assume that the value of the variable \(m\) is changed from \(m^{\prime}\) to \(m^{\prime\prime}=m^{\prime}+1\). Then, the interval \(I^{\prime}_{v_{m^{\prime\prime}}}\) is \"flipped\" from right to left centered at \(m^{\prime\prime}\). More precisely, changing from \(m^{\prime}\) to \(m^{\prime\prime}=m^{\prime}+1\) means changing \(I^{\prime}_{v_{m^{\prime\prime}}}\) from \([m^{\prime\prime}..\ell+m^{\prime\prime}-1]\) to \([-\ell+m^{\prime\prime}+1..m^{\prime\prime}]\), or equivalently, from \(L(I^{\prime}_{v_{m^{\prime\prime}}})=m^{\prime\prime}\) to \(R(I^{\prime}_{v_{m^{\prime\prime}}})=m^{\prime\prime}\).