4 citations · 5 across the 5 of their papers we have counts for
5 papers · 1 filter
Single-Exponential FPT Algorithms for Enumerating Secluded -Free Subgraphs and Deleting to Scattered Graph Classes
Bart M. P. Jansen, Jari J. H. de Kroon, Michał Włodarczyk
The celebrated notion of important separators bounds the number of small -separators in a graph which are 'farthest from ' in a technical sense. In this paper, we introdu…
Finding Long Directed Cycles Is Hard Even When DFVS Is Small Or Girth Is Large
Ashwin Jacob, Michał Włodarczyk, Meirav Zehavi
We study the parameterized complexity of two classic problems on directed graphs: Hamiltonian Cycle and its generalization {\sc Longest Cycle}. Since 2008, it is known that Hamilto…
Planar Disjoint Paths, Treewidth, and Kernels
Michał Włodarczyk, Meirav Zehavi
In the Planar Disjoint Paths problem, one is given an undirected planar graph with a set of vertex pairs and the task is to find pairwise vertex-disjoint paths…
5-Approximation for -Treewidth Essentially as Fast as -Deletion Parameterized by Solution Size
Bart M. P. Jansen, Jari J. H. de Kroon, Michal Wlodarczyk
The notion of -treewidth, where is a hereditary graph class, was recently introduced as a generalization of the treewidth of an undirected graph. Roughly…
Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth
Michal Wlodarczyk
In Chordal/Interval Vertex Deletion we ask how many vertices one needs to remove from a graph to make it chordal (respectively: interval). We study these problems under the paramet…