## 6 Results  
### Simpler Proof of the Inapproximability of \(\{\)Cut, Path, Tree\(\}\)-Widths  
As mentioned in Section 1, in [9], [PERSON] et al. demonstrated that under SSEH there are no constant factor approximation algorithms for cut-width, path-width, and tree-width. In this subsection, we show the same result in a different way from that of [PERSON] et al. The difference is as follows. Recall first  
Figure 1: Scheme showing how to prove the inapproximability. (\(\mathit{gw}_{1}\to\mathit{gw}_{2}\) means that \(\mathit{gw}_{1}\preceq\mathit{gw}_{2}\)). the relations \(cutw(G)\geq pw(G)\geq tw(G)\). To show the approximation, hardness, completeness, and soundness should be proved (see Section 4). To prove completeness, [PERSON] et al. gave an upper threshold of cut-width, and we just use their upper threshold, so there is no difference in this part. To prove soundness, they gave a lower threshold of tree-width. To obtain the lower threshold, they used the lower bound of \"1/2-vertex separator\", which is a well-known lower bound of tree-width. Instead of the 1/2-vertex separator, we employ the vertex boundary width, which is also known as a lower bound of tree-width. The most obvious difference is that they used an auxiliary graph \(G^{\prime}\) produced from an input graph \(G\) to show a lower bound of 1/2-vertex separator of \(G^{\prime}\), while in our case, we do not need an auxiliary graph. In this sense, our proof is simpler than that of [PERSON] et al. (2014). To be self-contained, we review the proof of the completeness of Theorem 4.1 in [9]. **Lemma 2** (Completeness of Theorem 4.1 in [9]). : _Let \(q=\frac{1}{\varepsilon}\). Let \(G=(V,E)\) be \(d\)-regular and a YES instance in Problem 1, where \(d\) is an universal constant. Then, \(cutw(G)\leq c_{c}\varepsilon|E|\) holds for some universal constant \(c_{c}\)._  
Proof. : Since \(G\) is a YES instance, we have  
\[|E(S_{i},V\backslash S_{i})|=\Phi_{G}(S_{i})\times d|S_{i}|=\Phi_{G}(S_{i}) \times d\frac{|V|}{q}=\Phi_{G}(S_{i})\times\frac{2|E|}{q}\leq\frac{4\varepsilon |E|}{q}.\]  
Hence, the number of edges whose endpoints do not belong to the same partition \(S_{i}\) is upper-bounded as follows:  
\[\frac{1}{2}\sum_{i=1}^{q}|E(S_{i},V\backslash S_{i})|\leq\frac{1}{2}\sum_{i=1} ^{q}\frac{4\varepsilon|E|}{q}\leq 2\varepsilon|E|.\]  
From \(\frac{1}{q}=\varepsilon\), we have \(|S_{i}|=\varepsilon|V|\). Hence, \(|E(S_{i},S_{i})|\) is at most \(\frac{d|S_{i}|}{2}=\frac{d\varepsilon|V|}{2}=\varepsilon|E|\). Thus, by considering an ordering in which \(u\) comes before \(v\) for any vertices of \(u\in S_{i}\) and \(v\in S_{j}\) with \(i<j\), we have \(cutw(G)\leq 3\varepsilon|E|\) (i.e., \(c_{c}=3\)). We now show the soundness in Lemma 3. **Lemma 3**. : _Let \(G=(V,E)\) be a NO instance stated in Problem 1. Then, for all \(\frac{|V|}{4}\leq i\leq\frac{|V|}{2}\),_  
* \(\min_{i}b_{e}(i,G)\geq\frac{c}{2}\sqrt{\varepsilon}|E|\)_, and_
* \(\min_{i}b_{v}(i,G)\geq\frac{c}{2d}\sqrt{\varepsilon}|E|\)__  
_hold, where \(c\) is the constant in the NO instance in Problem 1._  
Proof. : For each \(\frac{|V|}{4}\leq i\leq\frac{|V|}{2}\), let \(S^{i}\) be a set such that \(b_{e}(i,G)=|E(S^{i},\overline{S^{i}})|\) and \(|S^{i}|=i\). Then, for each \(i\), we have \(b_{e}(i,G)=|E(S^{i},\overline{S^{i}})|=\Phi_{G}(S^{i})\times d|S^{i}|\geq c \sqrt{\varepsilon}\times d\times i\geq c\sqrt{\varepsilon}\times d\times\frac {|V|}{4}=\frac{\varepsilon}{2}\sqrt{\varepsilon}\times|E|\). Let \(S^{i}\) be a set such that \(b_{v}(i,G)=|N(S^{i})|\) and \(|S^{i}|=i\). From the above and the fact that \(|E(S,\overline{S})|\leq|N(S)|\times d\), we have  
\[\min_{\frac{|V|}{4}\leq i\leq\frac{|V|}{2}}b_{v}(i,G) = \min_{\frac{|V|}{4}\leq i\leq\frac{|V|}{2}}|N(S^{i})|\geq\min_{ \frac{|V|}{4}\leq i\leq\frac{|V|}{2}}\frac{|E(S^{i},\overline{S^{i}})|}{d}\] \[\geq \frac{1}{d}\times\min_{\frac{|V|}{4}\leq i\leq\frac{|V|}{2}}|E(S^ {i},\overline{S^{i}})|\geq\frac{1}{d}\times\frac{c}{2}\sqrt{\varepsilon}|E|.\]  
**Theorem 2**.