8 papers
Trade-off between spread and width for tree decompositions
Hans L. Bodlaender, Carla Groenland, Sergey Norin +1
The spread of a vertex in a tree decomposition is the number of bags that contain . We study the trade-off between spread and width in tree decompositions, answering every o…
Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters
Hans L. Bodlaender, Carla Groenland, Michał Pilipczuk
We investigate the parameterized complexity of Binary CSP parameterized by the vertex cover number and the treedepth of the constraint graph, as well as by a selection of related m…
List Colouring Trees in Logarithmic Space
Hans L. Bodlaender, Carla Groenland, Hugo Jacob
We show that List Colouring can be solved on -vertex trees by a deterministic Turing machine using bits on the worktape. Given an -vertex graph and a li…
On the parameterized complexity of computing tree-partitions
Hans L. Bodlaender, Carla Groenland, Hugo Jacob
We study the parameterized complexity of computing the tree-partition-width, a graph parameter equivalent to treewidth on graphs of bounded maximum degree. On one hand, we can obta…
On the Complexity of Problems on Tree-structured Graphs
Hans L. Bodlaender, Carla Groenland, Hugo Jacob +2
In this paper, we introduce a new class of parameterized problems, which we call XALP: the class of all parameterized problems that can be solved in time and $f(k)\l…
XNLP-completeness for Parameterized Problems on Graphs with a Linear Structure
Hans L. Bodlaender, Carla Groenland, Hugo Jacob +2
In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing -hardness proofs for the…
Parameterized Complexities of Dominating and Independent Set Reconfiguration
Hans L. Bodlaender, Carla Groenland, Céline M. F. Swennenhuis
We settle the parameterized complexities of several variants of independent set reconfiguration and dominating set reconfiguration, parameterized by the number of tokens. We show t…
Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space
Hans L. Bodlaender, Carla Groenland, Jesper Nederlof +1
Let XNLP be the class of parameterized problems such that an instance of size n with parameter k can be solved nondeterministically in time and space (…