Jesper Nederlof

activity

20112026

most citedOn Problems as Hard as CNFSAT

121 citations · 181 across the 38 of their papers we have counts for

collaborators

Showing 2019Show all

5 papers · 1 filter

cs.DS2019

Parameterized Complexity of Partial Scheduling

Jesper Nederlof, Céline Swennenhuis

We study a natural variant of scheduling that we call \emph{partial scheduling}: In this variant an instance of a scheduling problem along with an integer $k$ is given and one seek…

cs.DS2019

Detecting Feedback Vertex Sets of Size $k$ in $O^{⋆} (2. 7^{k})$ Time

Jason Li, Jesper Nederlof

In the Feedback Vertex Set problem, one is given an undirected graph $G$ and an integer $k$ , and one needs to determine whether there exists a set of $k$ vertices that intersects a…

cs.DS2019

Equal-Subset-Sum Faster Than the Meet-in-the-Middle

Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz +1

In the Equal-Subset-Sum problem, we are given a set $S$ of $n$ integers and the problem is to decide if there exist two disjoint nonempty subsets $A, B \subseteq S$ , whose elements…

cs.DS2019

Detecting and Counting Small Patterns in Planar Graphs in Subexponential Parameterized Time

Jesper Nederlof

We present an algorithm that takes as input an $n$ -vertex planar graph $G$ and a $k$ -vertex pattern graph $P$ , and computes the number of (induced) copies of $P$ in $G$ in $2^{O(k/…

cs.DS2019

Hamiltonicity below Dirac's condition

Bart M. P. Jansen, László Kozma, Jesper Nederlof

Dirac's theorem (1952) is a classical result of graph theory, stating that an $n$ -vertex graph ( $n \geq 3$ ) is Hamiltonian if every vertex has degree at least $n /2$ . Both the value…

Parameterized Complexity of Partial Scheduling

Detecting Feedback Vertex Sets of Size k in O⋆(2.7k) Time

Equal-Subset-Sum Faster Than the Meet-in-the-Middle

Detecting and Counting Small Patterns in Planar Graphs in Subexponential Parameterized Time

Hamiltonicity below Dirac's condition

Detecting Feedback Vertex Sets of Size $k$ in $O^{⋆} (2. 7^{k})$ Time