## 6 Results
### Inapproximability of Rank, Clique, Boolean, and Min-Widths  
Theorem 3.1.: _Under SSEH, it is NP-hard to approximate rank and clique-widths of a graph to within a constant factor in polynomial time._  
Proof. : Let \(G=(V,E)\) be a YES instance stated in Problem 1, and \(M\) an adjacency matrix of \(G\). Then, from the fact that \(rw(G)\leq tw(G)+1\leq pw(G)+1\)[29] and Lemma 2, we have \(rw(G)\leq 2\times pw(G)\leq c\times\varepsilon|E|\) for some constant \(c\), from which follows the completeness. Now, let \(G=(V,E)\) be a NO instance stated in Problem 1. Hence, for any \(S\subseteq V\) such that \(\frac{|V|}{10}\leq|S|\leq\frac{9|V|}{10}\), \(\Phi_{G}(S)\geq c\sqrt{\varepsilon}\) holds, where \(c\) is the constant in the NO instance in Problem 1. To prove the soundness, we will show that \(rw(G)\geq c^{\prime}\sqrt{\varepsilon}|E|\) for some constant \(c^{\prime}\). Let \((T,f_{T})\) be an optimal decomposition tree of \(G\), (i.e., \(\max\limits_{e\in E(T)}rank(M[(V\backslash e)_{1},(V\backslash e)_{2}])=rw(G)\)). Since \(T\) is a subcubic tree, \(T\) has an edge \(e\) such that \(\min\{|(V\backslash e)_{1}|,\,|(V\backslash e)_{2}|\}\geq\frac{|V|-1}{3}\). For graphs with \(|V|\geq 10\), we have \(\frac{|V|-1}{3}\geq 0.9\cdot\frac{|V|}{3}\). Denote \((V\backslash e)_{1}\) by \(A\) and \((V\backslash e)_{2}\) by \(B\). As \(rw(G)\geq rank(M[A,B])\), it is sufficient to show that \(rank(M[A,B])\geq c^{\prime}\sqrt{\varepsilon}|E|\) for some \(c^{\prime}\). Since \(\min\{\mathsf{vol}(A),\mathsf{vol}(B)\}=d\times\min\{|A|,|B|\}\geq d\times\frac {|V|-1}{3}\geq 0.9\times d\times\frac{|V|}{3}\) holds. Thus, \(|E(A,\overline{A})|=\min\{\mathsf{vol}(A),\mathsf{vol}(B)\}\times\Phi_{G}(A) \geq 0.9d\frac{|V|}{3}\times c\sqrt{\varepsilon}=0.9\times\frac{2|E|}{3} \times c\sqrt{\varepsilon}\). Since the number of nonzero elements (i.e., 1's) of \(M\) equals \(|E(A,B)|\), the number of nonzero elements is at least \(c\sqrt{\varepsilon}\times 0.9\times\frac{2|E|}{3}\). Meanwhile, the number of nonzero elements in each row and/or column of \(M\) is at most \(d\), because \(G\) is \(d\)-regular. Hence, by Lemma 1, we have \(rank(M[A,B])\geq\frac{2c}{3d^{2}}\times 0.9\times\sqrt{\varepsilon}|E|\) as desired (i.e., \(c^{\prime}=\frac{2c}{3d^{2}}\times 0.9\)). The approximation hardness of clique-width follows from the relations \(cliw(G)\leq pw(G)+2\)[30] and \(rw(G)\leq cliw(G)\)[31] (see also inequalities (A4) and (A3) in Appendix A). As stated in Theorem 1, the hardness can also be obtained from the approximation hardness of tree-width. Theorem 3.2.: _Under SSEH, it is NP-hard to approximate mim and boolean-widths of a graph to within a constant factor in polynomial time._  
Proof. : The proof is quite similar to that of Theorem 3. It is known that \(mimw(G)\leq bow(G)\)[32] and \(bow(G)\leq tw(G)+1\)[33] (see also inequalities (A6) and (A7) in Appendix A). From the relations, it is sufficient to show that, given a NO instance \(G=(V,E)\), \(mimw(G)\geq c^{\prime}\sqrt{\varepsilon}|E|\) for some constant \(c^{\prime}\). Let \((T,f_{T})\) be an optimal decomposition tree of \(G\), and \(e\) be an edge such that \(\min\{|(V\backslash e)_{1}|,\,|(V\backslash e)_{2}|\}\geq\frac{|V|-1}{3}\). Note that since \(T\) is a subcubic tree, there exists such edge \(e\). Without loss of generality, we may assume that \(|(V\backslash e)_{1}|\leq|(V\backslash e)_{2}|\). Let \(A\) denote \((V\backslash e)_{1}\). As \(\frac{|V|-1}{3}\leq|A|\leq\frac{2|V|+1}{3}\), \(\Phi_{G}(A)\geq c\sqrt{\varepsilon}\) holds. Since \(\min\{\mathsf{vol}(A),\mathsf{vol}(\overline{A})\}=d\times\min\{|A|,|\overline {A}|\}=d\times|A|\geq d\times\frac{|V|-1}{3}\) holds, we have \(|E(A,\overline{A})|=\min\{\mathsf{vol}(A),\mathsf{vol}(\overline{A})\}\times \Phi_{G}(A)\geq d\frac{|V|-1}{3}\times c\sqrt{\varepsilon}=c\sqrt{\varepsilon} \frac{2|E|-d}{3}\geq c\sqrt{\varepsilon}\frac{|E|}{3}\). Pick any edge \(e\) from \(E(A,\overline{A})\).