Score: 0
Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
Published: July 1, 2025 |
arXiv ID: 2507.00612v1
By: Benjamin Bergougnoux, Lars Jaffke
Potential Business Impact:
Makes hard computer problems stay hard for computers.
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.
Similar Papers
86%
A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers
Discrete Mathematics
Finds paths in tricky maps, even with rules.
9 Oct 2025
0
86%
A Graph Width Perspective on Partially Ordered Hamiltonian Paths
Discrete Mathematics
Finds best order for tasks with rules.
5 Mar 2025
0
86%
On the hardness of recognizing graphs of small mim-width and its variants
Discrete Mathematics
Makes hard computer problems solvable, even for small cases.
5 Dec 2025
0
Page Count
11 pages
Category
Computer Science:
Computational Complexity