2 papers
cs.CC2025
Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
Benjamin Bergougnoux, Lars Jaffke
We prove that Hamiltonian Path and Hamiltonian Cycle are NP-hard on graphs of linear mim-width 26, even when a linear order of the input graph with mim-width 26 is provided togethe…
cs.CC2025
Mim-Width is paraNP-complete
Benjamin Bergougnoux, Ãdouard Bonnet, Julien Duron
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-Widt…