Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard

July 01, 2025 · The Ethereal · 🏛 International Symposium on Parameterized and Exact Computation

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Benjamin Bergougnoux, Lars Jaffke arXiv ID 2507.00612 Category cs.CC: Computational Complexity Cross-listed cs.DS Citations 0 Venue International Symposium on Parameterized and Exact Computation Last Checked 3 months ago
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.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 🎉 Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

📜 Similar Papers

In the same crypt — Computational Complexity