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

b-Coloring Parameterized by Clique-Width

with Paloma T. Lima and Daniel Lokshtanov
preprint (2020)

Well-partitioned chordal graphs: obstruction set and disjoint paths

with Jungho Ahn, O-joung Kwon, and Paloma T. Lima
preprint (2020)

Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach

with Mateus de Oliveira Oliveira and Hans Raj Tiwary
preprint (2020)

Conference Proceedings without Published Full Version

Hedonic Seat Arrangement Problems (Extended Abstract)

with Hans L. Bodlaender, Tesshu Hanaka, Hirotaka Ono, Yota Otachi, and Tom C. van der Zanden
AAMAS 2020 (to appear) | arXiv

Typical Sequences Revisited - Computing Width Parameters of Graphs

with Hans L. Bodlaender and Jan Arne Telle
STACS 2020 | arXiv | bibtex

On Weak Isomorphism of Rooted Vertex-Colored Graphs

with Mateus de Oliveira Oliveira
WG 2018 | bibtex

Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems

with Bart M. P. Jansen
CIAC 2017 | arXiv | bibtex

open access

Publications

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

with Paloma T. Lima
Theoretical Computer Science (2020) | MFCS 2019 | [pdf] | bibtex

Mim-Width II. The Feedback Vertex Set Problem

with O-joung Kwon and Jan Arne Telle
Algorithmica (2020) | STACS 2018 | [pdf] | bibtex

Mim-Width III. Graph Powers and Generalized Distance Domination Problems

with O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle
Theoretical Computer Science (2019) | IPEC 2018 | [pdf] | bibtex

FPT Algorithms for Diverse Collections of Hitting Sets

with Julien Baste, Tomáš Masařík, Geevarghese Philip, and Günter Rote
Algorithms (2019) | bibtex
SI: New Frontiers in Parameterized Complexity and Algorithms

What is known about Vertex Cover Kernelization?

with Michael R. Fellows, Aliz Kiraly, Frances A. Rosamond, and Mathias Weller
LNCS (2018) | arXiv | bibtex
Note: The arXiv-version fixes a flaw in Redcuction R.8 of the LNCS version.

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

with Hans L. Bodlaender, Pinar Heggernes, and Jan Arne Telle
European Journal of Combinatorics (2017) | IPEC 2015 | bibtex
Note: The paper contains results from another extended abstract that appeared at EUROCOMB 2015.

open access

Notes

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

with O-joung Kwon and Jan Arne Telle
arXiv (2017) | bibtex