4 papers
Dynamic programming on bipartite tree decompositions
Lars Jaffke, Laure Morelle, Ignasi Sau +1
We revisit a graph width parameter that we dub bipartite treewidth (btw). Bipartite treewidth can be seen as a common generalization of treewidth and the odd cycle transversal numb…
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…
Hedonic Seat Arrangement Problems
Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke +3
In this paper, we study a variant of hedonic games, called \textsc{Seat Arrangement}. The model is defined by a bijection from agents with preferences for each other to vertices in…
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 Vil…