Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis (Q1712018): Difference between revisions

Summary: \textit{Y. Wu} et al. [J. Artif. Intell. Res. (JAIR) 49, 569--600 (2014; Zbl 1361.68173)] showed that under the small set expansion hypothesis (SSEH) there is no polynomial time approximation algorithm with any constant approximation factor for several graph width parameters, including tree-width, path-width, and cut-width [loc. cit.]. In this paper, we extend this line of research by exploring other graph width parameters: We obtain similar approximation hardness results under the SSEH for rank-width and maximum induced matching-width, while at the same time we show the approximation hardness of carving-width, clique-width, NLC-width, and boolean-width. We also give a simpler proof of the approximation hardness of tree-width, path-width, and cut-width than that of Wu et al. [loc. cit.].