Bart Jansen
Department / Institute
Group
![](https://assets.w3.tue.nl/w/fileadmin/_processed_/5/1/csm_c70bfd41f7d835b4570043e5a1463653_9f1bc6930f.jpg)
RESEARCH PROFILE
Bart Jansen is an Associate Professor in the Department of Mathematics and Computer Science at Eindhoven University of Technology (TU/e). His areas of expertise include algorithms, complexity theory, and graph theory. Bart’s research interests mainly concern parameterized (graph) algorithmics, with a special focus on provably effective preprocessing (kernelization). He is a member of NETWORKS, an NWO Gravitation project spanning multiple universities in the Netherlands. Its goal is to investigate the interplay between algorithms and stochastics to tackle complex problems on networks.
Bart’s main focus is on understanding the power of data reduction. In practice, the search for the exact solution to an NP-complete problem is often accelerated by orders of magnitude by adding a preprocessing phase. Before attempting to solve the problem, it is simplified by repeatedly applying reduction rules that do not change the answer. How can such reduction rules be developed systematically, how can we explain their success, and how can we estimate what types of reduction rules are useful for a certain application? These are questions that Bart attacks on a daily basis.
Investigating efficient preprocessing algorithms is like exploring the lost continent of polynomial time. For decades, researchers believed there are no polynomial-time algorithms which are guaranteed to be useful in the search for exact answers to NP-complete problems. But we’re now discovering there is a rich variety of preprocessing algorithms to be found!”
ACADEMIC BACKGROUND
Bart Jansen received an MSc in Applied Computing Science from Utrecht University, the Netherlands, in 2009. He received a PhD from the same university in 2013. After working for one year as a postdoctoral researcher at the University of Bergen, Norway, he returned to the Netherlands to become Assistant Professor at TU/e. Bart received a VENI grant from NWO. In June 2014, Bart was awarded the Christiaan Huygens Prize in ICT.
Bart served on the program committee of numerous international algorithmic conferences such as SODA, ICALP, ESA, WG, and IPEC. He co-chaired the International Symposium on Parameterized and Exact Computation in 2019. He is an Associate Editor for ACM Transactions on Algorithms (TALG), and on the Steering Committee of PACE (Parameterized Algorithms and Computational Experiments Challenge). He was invited speaker at a wide range of events, such as the 10th Workshop on Graph Classes, Optimization, and Width Parameters (GROW 2022), the workshop on Advanced in Parameterized Graph Algorithms (2022), and the Workshop on Kernelization (2019).
Key Publications
-
Turing kernelization for finding long paths and cycles in restricted graph classes
Journal of Computer and System Sciences (2017) -
Kernelization lower bounds by cross-composition
SIAM Journal on Discrete Mathematics (2014) -
Fine-grained complexity analysis of two classic TSP variants
(2016) -
Approximation and kernelization for chordal vertex deletion
(2017) -
Uniform kernelization complexity of hitting forbidden minors
ACM Transactions on Algorithms (2017)
Current Educational Activities
Ancillary Activities
No ancillary activities