114 citations · 306 across the 50 of their papers we have counts for
5 papers · 1 filter
Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time
Hans L. Bodlaender, Marek Cygan, Stefan Kratsch +1
It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in 2^{O(tw)}|V|^{O(1)} time for graphs G=(V,E) with a given tree decomposition…
Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs
Stefan Kratsch, Pascal Schweitzer
We study the complexity of the Graph Isomorphism problem on graph classes that are characterized by a finite number of forbidden induced subgraphs, focusing mostly on the case of t…
Kernel Bounds for Structural Parameterizations of Pathwidth
Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
Assuming the AND-distillation conjecture, the Pathwidth problem of determining whether a given graph G has pathwidth at most k admits no polynomial kernelization with respect to k.…
Kernelization Lower Bounds By Cross-Composition
Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
We introduce the cross-composition framework for proving kernelization lower bounds. A classical problem L AND/OR-cross-composes into a parameterized problem Q if it is possible to…
Fixed-parameter tractability of multicut in directed acyclic graphs
Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk +1
The MULTICUT problem, given a graph G, a set of terminal pairs T={(s_i,t_i) | 1 <= i <= r} and an integer p, asks whether one can find a cutset consisting of at most p non-terminal…