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.

News

July 10
...and in the Parameterized Complexity Seminar on July 13, at 12:30 GMT+2 (16:00 IST).
June 25
Paloma Lima will give a talk about well-partitioned chordal graphs in the Graphes en Rhône-Alpes et Auvergne seminar on July 02, at 14:30 GMT+2.
June 1
Hans Bodlaender will give a talk on our joint work on typical sequences in the Frontiers of Parameterized Complexity seminar series on June 4, at 17:00 GMT+2.
May 20
O-joung Kwon gave a survey talk on mim-width at the IBS DIMAG seminar series. You can watch the recording here.

Recent Manuscripts

b-Coloring Parameterized by Clique-Width

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

Conference Proceedings without Published Full Version

Structural Parameterizations of Clique Coloring

with Paloma T. Lima and Geevarghese Philip
MFCS 2020 (to appear) | arXiv

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

with Mateus de Oliveira Oliveira and Hans Raj Tiwary
MFCS 2020 (to appear) | arXiv

Well-partitioned chordal graphs: obstruction set and disjoint paths

with Jungho Ahn, O-joung Kwon, and Paloma T. Lima
WG 2020 (to appear) | arXiv

Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory

with Julien Baste, Michael R. Fellows, Tomáš Masařík, Mateus de Oliveira Oliveira, Geevarghese Philip, and Frances A. Rosamond
IJCAI 2020 | arXiv | bibtex

Hedonic Seat Arrangement Problems

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

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