Recognizing Mim-Width and Its Variants Is NP-Complete at Every Fixed Width

We study the computational complexity of recognizing graphs of bounded mim-width and three related width parameters: sim-width, one-sided mim-width (omim-width), and Omim-width. We prove that, for each of these four parameters and every fixed integer k ≥ 1, deciding whether a graph has width at most k is NP-complete. Our first contribution establishes NP-completeness of recognizing graphs of mim-width at most one, resolving an open recognition problem. The proof uses a reduction from NAE-3SAT through an ordered hierarchical reconstruction problem, a rigid frame construction, and a graph gadget combining an exterior chain with a hub vertex. Our second contribution develops polynomial-time width-shift constructions that transfer recognition hardness from width one to every fixed width. For sim-width, omim-width, and Omim-width, these constructions build on previously published width-one hardness results. We also establish structural limitations on local gap-amplification constructions. Recognition of the linear variants and stronger approximation-hardness questions remain open. Version: Preprint v2, November 2026. Supplementary material: Reproduction code, computational certificates, experimental logs, and an independent AI-assisted adversarial review report are provided. Research integrity statement: This manuscript has not undergone formal peer review. The research, proof development, and computational verification involved extensive AI assistance, disclosed in the manuscript. The author is responsible for the content.