29 citations · 63 across the 22 of their papers we have counts for
Showing 2025Show all
2 papers · 1 filter
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.DS2025★ 1 cited
A Parameterized Complexity Analysis of Bounded Height Depth-first Search Trees
Lars Jaffke, Paloma T. de Lima, Wojciech Nadara +1
Computing bounded depth decompositions is a bottleneck in many applications of the treedepth parameter. The fastest known algorithm, which is due to Reidl, Rossmanith, Sánchez Vill…