## 4 Method for Showing Inapproximability  
In this section, we explain the useful method which is used implicitly in [9] to prove the inapproximability of width parameters in a unified setting. Through the remainder of this section, \(gw\) denotes a graph width parameter such that determining \(gw\) is a minimization problem and \(P\) denotes any polynomial time computable parameter of \(G\), typically \(|V|\) or \(|E|\). That is, the graph parameters \(gw\) and \(P\) are functions from graphs to the natural numbers such that isomorphic graphs are mapped to the same number.  
To show the approximation hardness of \(gw\), it is sufficient to prove that there are constants \(c_{Y}\) and \(c_{N}\) such that for any graph \(G\),\(gw(G)\leq c_{Y}\varepsilon P\) holds if \(G\) is a YES instance in Problem 1 (i.e., completeness), and \(gw(G)\geq c_{N}\sqrt{\varepsilon}P\) holds if \(G\) is a NO instance in Problem 1 (i.e., soundness), where \(\varepsilon\) is the same as in Problem 1. We will refer to such \(c_{Y}\varepsilon P\) (\(c_{N}\sqrt{\varepsilon}P\), resp.) as _upper threshold_ (_lower threshold_, resp.).  
Suppose that \(gw(G)\) can be approximated within a constant factor in polynomial time. That is, there is a constant \(\rho>0\) for which there is an approximation algorithm \(A\) such that for any graph \(G\), \(A\) outputs a value \(A(G)\) satisfying \(gw(G)\leq A(G)\leq\rho\cdot gw(G)\). Then, take \(\varepsilon\) such that \(\frac{1}{\rho}>\frac{c_{Y}\sqrt{\varepsilon}}{c_{N}}\). That is, \(\varepsilon<\left(\frac{c_{N}}{c_{Y}}\cdot\frac{1}{\rho}\right)^{2}\). Then, the following Algorithm 1, which uses the approximation algorithm \(A\) as a subroutine, solves Problem 1.  
```
Input: a graph \(G\) Output: YES/NO
1 compute an approximate solution \(A(G)\) of \(gw(G)\);
2 if\(A(G)<c_{N}\sqrt{\varepsilon}P\)then
3 output \"\(G\) is a YES instance in Problem \(1\)\"
4 else
5 output \"\(G\) is a NO instance in Problem \(1\)\"
6 end if
```  
**Algorithm 1** DeciInstByAlg\(A(G)\)  
The correctness of Algorithm 1 can be explained as follows. In the case of \"\(A(G)<c_{N}\sqrt{\varepsilon}P\)\", from \(gw(G)\leq A(G)<c_{N}\sqrt{\varepsilon}P\), we can guarantee that \(G\) is not a NO instance by the soundness condition. In the case of \"\(A(G)\geq c_{N}\sqrt{\varepsilon}P\)\", from \(gw(G)\geq\frac{A(G)}{\rho}\geq\frac{c_{N}\sqrt{\varepsilon}}{\rho}P>c_{N} \sqrt{\varepsilon}\cdot\frac{c_{Y}\sqrt{\varepsilon}}{c_{N}}P\geq c_{Y} \varepsilon P\), we can conclude that \(G\) is not a YES instance by the completeness condition.  
It is worth mentioning that for graph width parameters \(gw_{i}\) (\(1\leq i\leq 3\)) such that \(gw_{1}(G)\preceq gw_{2}(G)\preceq gw_{3}(G)\) for any graph \(G\), the approximation hardness of \(gw_{i}\) (\(1\leq i\leq 3\)) can be shown by just showing both the completeness for \(gw_{3}\) and soundness for \(gw_{1}\), where \(gw_{i}(G)\preceq gw_{i+1}(G)\) means that there exists a constant \(c\) such that \(gw_{i}(G)\leq c\cdot gw_{i+1}(G)\) for any \(G\). Figure 1 illustrates the unified setting: two width parameters \(gw_{u}\) and \(gw_{l}\) such that \(gw_{u}\) is arranged above \(gw_{l}\) are linked by a line if \(gw_{l}\preceq gw_{u}\) holds. In the figure, _lclw_ means _linear clique-width_, and the left (right, resp.) side illustrates a scheme of proofs for the inapproximability in [9] (this paper, resp.). The relations among width parameters illustrated in Figure 1 can be confirmed from the inequalities in Appendix A.