Lars Jaffke

Lars Jaffke

Theoretical Computer Scientist

About Me

I am a PhD Student in (Multivariate) Algorithmics in the algorithms group at the University of Bergen. My advisors are Michael Fellows and Jan Arne Telle. My main research interests revolve around graphs in algorithms.

Recent Manuscripts

Diversity in Combinatorial Optimization

Julien Baste, Michael R. Fellows, Lars Jaffke, Tomáš Masařík, Mateus de Oliveira Oliveira, Geevarghese Philip, and Frances A. Rosamond
preprint (2019)
arXiv

A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs

Lars Jaffke and Paloma T. Lima
preprint (2018)
arXiv

Journal Articles

Definability Equals Recognizability for k-Outerplanar Graphs and l-Chordal Partial k-Trees

Lars Jaffke, Hans L. Bodlaender, Pinar Heggernes, and Jan Arne Telle
European Journal of Combinatorics, Volume 66, Pages 191-234 (2017)
ScienceDirect bibtex

Conference Proceedings and Collections

Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded Mim-Width

Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle
Proc. 13th IPEC, Vol. 115 of LIPIcs, Pages 6:1-6:14 (2018)
arXiv LIPIcs bibtex

On Weak Isomorphism of Rooted Vertex-Colored Graphs

Lars Jaffke and Mateus de Oliveira Oliveira
Proc. 44th WG, Vol. 11159 of LNCS, Pages 266-278 (2018)
LNCS bibtex

What is known about Vertex Cover Kernelization?

Michael R. Fellows, Lars Jaffke, Aliz Kiraly, Frances A. Rosamond, and Mathias Weller
Adventures Between Lower Bounds and Higher Altitudes, Vol. 11011 of LNCS, Pages 330-356 (2018)
arXiv LNCS bibtex
Note: The arXiv-version fixes a flaw in Redcuction R.8 of the LNCS version.

A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width

Lars Jaffke, O-joung Kwon, and Jan Arne Telle
Proc. 35th STACS, Vol. 96 of LIPIcs, Pages 42:1-42:14 (2018)
arXiv LIPIcs bibtex

Polynomial-Time Algorithms for the Longest Induced Path and Induced Disjoint Path Problems on Graphs of Bounded Mim-Width

Lars Jaffke, O-joung Kwon, and Jan Arne Telle
Proc. 12th IPEC, Vol. 89 of LIPIcs, Pages 21:1-21:13 (2017)
arXiv LIPIcs bibtex

Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems

Lars Jaffke and Bart M. P. Jansen
Proc. 10th CIAC, Vol. 10236 of LNCS, Pages 345-356 (2017)
arXiv LNCS bibtex

Definability Equals Recognizability for k-Outerplanar Graphs

Lars Jaffke and Hans L. Bodlaender
Proc. 10th IPEC, Vol. 43 of LIPIcs, Pages 175-186 (2015)
LIPIcs bibtex

Notes

A note on the complexity of Feedback Vertex Set parameterized by mim-width

Lars Jaffke, O-joung Kwon, and Jan Arne Telle
arXiv (2017) bibtex