On the hardness of recognizing graphs of small mim-width and its variants

Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye

The mim-width of a graph is a powerful structural parameter that, when bounded by a constant, allows several hard problems to be polynomial-time solvable - with a recent meta-theor…