Mim-Width Is paraNP-Complete
Benjamin Bergougnoux, Édouard Bonnet, Julien Duron · arXiv (Cornell University) · 2025
We show that it is NP-hard to distinguish graphs of linear mim-width at most 1211 from graphs of sim-width at least 1216. This implies that Mim-Width, Sim-Width, One-Sided Mim-Width, and their linear counterparts are all paraNP-complete, i.e., NP-complete to compute even when upper bounded by a constant. A key intermediate problem that we introduce and show NP-complete, Linear Degree Balancing, inputs an edge-weighted graph G and an integer τ, and asks whether V(G) can be linearly ordered such that every vertex of G has weighted backward and forward degrees at most τ.