{"ID":2899578,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.00612","arxiv_id":"2507.00612","title":"Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard","abstract":"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 together with input. This fills a gap left by a broken proof of the para-NP-hardness of Hamiltonicity problems parameterized by mim-width.","short_abstract":"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 together with input. This fills a gap left by a broken proof of the para-NP-hardness of Hamiltonicity problems parameterized by mim-width.","url_abs":"https://arxiv.org/abs/2507.00612","url_pdf":"https://arxiv.org/pdf/2507.00612v2","authors":"[\"Benjamin Bergougnoux\",\"Lars Jaffke\"]","published":"2025-07-01T09:44:31Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}