Inapproximability of Rank, Clique, Boolean, and Maximum Induced Matching-Widths under Small Set Expansion Hypothesis
Wu Fly Veils et al.(2014) 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 (Wu et al.2014).In this paper, we extend this line of research by exploring other graph w