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

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 @article{JaffkeBodlaenderHeggernesTelle2017,
author = {Lars Jaffke and Hans L. Bodlaender and Pinar Heggernes and Jan Arne Telle},
title = {Recognizability Equals Definability for $k$-Outerplanar Graphs and $\ell$-Chordal Partial $k$-Trees},
journal = {European Journal of Combinatorics},
volume = {66},
pages = {191--234},
publisher = {Elsevier},
doi = {10.1016/j.ejc.2017.06.025},
url = {https://www.sciencedirect.com/science/article/pii/S0195669817301002},
month = {December},
year = {2017},
}
|-short @article{JaffkeBodlaenderHeggernesTelle2017,
author = {Lars Jaffke and Hans L. Bodlaender and Pinar Heggernes and Jan Arne Telle},
title = {Recognizability Equals Definability for $k$-Outerplanar Graphs and $\ell$-Chordal Partial $k$-Trees},
journal = {Eur. J. Combin.},
pages = {191--234},
year = {2017},
volume = {66}
}

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. IPEC 2018 (to appear)
arXiv

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 @InProceedings{JaffkeOliveira2018,
author = {Jaffke, Lars and Oliveira, Mateus de Oliveira},
title = {On Weak Isomorphism of Rooted Vertex-Colored Graphs},
booktitle = {Proceedings 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '18)},
editor = {Brandst\"{a}dt, Andreas and K\"{o}hler, Ekkehard and Meer, Klaus},
pages = {266--278},
publisher = {Springer},
series = {Lecture Notes In Computer Science (LNCS)},
volume = {11159},
month = {June 27 - 29,},
address = {Cottbus, Germany},
year = {2018},
}
|-short @InProceedings{JaffkeOliveira2018,
author = {Jaffke, Lars and Oliveira, Mateus de Oliveira},
title = {On Weak Isomorphism of Rooted Vertex-Colored Graphs},
booktitle = {WG '18},
pages = {266--278},
series = {LNCS},
volume = {11159},
year = {2018},
}

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)
LNCS bibtex @InCollection{FellowsEtAl2018,
author = {Fellows, Michael R. and Jaffke, Lars and Kir{\'a}ly, Al{\'i}z and Rosamond, Frances A. and Weller, Mathias},
title = {What Is Known About Vertex Cover Kernelization?},
editor = {B\"{o}ckenhauer, Hans-Joachim and Komm, Dennis and Unger, Walter},
booktitle = {Adventures Between Lower Bounds and Higher Altitudes. Essays Dedicated to Juraj Hromkovi\v{c} on the Occasion of His 60th Birthday},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {11011},
pages = {330--356},
publisher = {Springer},
year = {2018},
}
|-short @InCollection{FellowsEtAl2018,
author = {Fellows, Michael R. and Jaffke, Lars and Kir{\'a}ly, Al{\'i}z and Rosamond, Frances A. and Weller, Mathias},
title = {What Is Known About Vertex Cover Kernelization?},
booktitle = {Adventures Between Lower Bounds and Higher Altitudes},
series = {LNCS},
volume = {11011},
pages = {330--356},
year = {2018},
}

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 @InProceedings{JaffkeKwonTelle2018,
author = {Lars Jaffke and O-joung Kwon and Jan Arne Telle},
title = {{A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width}},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages = {42:1--42:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-062-0},
ISSN = {1868-8969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8534},
URN = {urn:nbn:de:0030-drops-85348},
doi = {10.4230/LIPIcs.STACS.2018.42},
annote = {Keywords: graph width parameters, graph classes, feedback vertex set, leaf powers}
}
|-short @InProceedings{JaffkeKwonTelle2018,
author = {Lars Jaffke and O-joung Kwon and Jan Arne Telle},
title = {A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width},
booktitle = {STACS '18},
pages = {42:1-42:14},
series = {LIPIcs},
year = {2018},
volume = {96}
}

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 @InProceedings{JaffkeKwonTelle2017,
author = {Lars Jaffke and O-joung Kwon and Jan Arne Telle},
title = {{Polynomial-Time Algorithms for the Longest Induced Path and Induced Disjoint Paths Problems on Graphs of Bounded Mim-Width}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {21:1--21:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Daniel Lokshtanov and Naomi Nishimura},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8564},
URN = {urn:nbn:de:0030-drops-85643},
doi = {10.4230/LIPIcs.IPEC.2017.21},
annote = {Keywords: graph width parameters, dynamic programming, graph classes, induced paths, induced topological minors}
}
|-short @InProceedings{JaffkeKwonTelle2017,
author = {Lars Jaffke and O-joung Kwon and Jan Arne Telle},
title = {Polynomial-Time Algorithms for the Longest Induced Path and Induced Disjoint Paths Problems on Graphs of Bounded Mim-Width},
booktitle = {IPEC '17},
pages = {21:1-21:13},
series = {LIPIcs},
year = {2017},
volume = {89}
}

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 @InProceedings{JaffkeJansen2017,
author={Jaffke, Lars and Jansen, Bart M. P.},
editor={Fotakis, Dimitris and Pagourtzis, Aris and Paschos, Vangelis Th.},
title={Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems},
booktitle={10th International Conference on Algorithms and Complexity (CIAC 2017)},
year={2017},
publisher={Springer International Publishing},
address={Cham},
pages={345--356},
series={Lecture Notes in Computer Science (LNCS)},
volume={10236},
isbn={978-3-319-57586-5},
doi={10.1007/978-3-319-57586-5_29},
url={https://link.springer.com/chapter/10.1007/978-3-319-57586-5_29}
}
|-short @InProceedings{JaffkeJansen2017,
author = {Jaffke, Lars and Jansen, Bart M. P.},
title = {Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems},
booktitle = {CIAC '17},
pages = {345--356},
series = {LNCS},
year = {2017},
volume = {10236}
}

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 @InProceedings{JaffkeBodlaender2015,
author = {Lars Jaffke and Hans L. Bodlaender},
title = {{Definability Equals Recognizability for k-Outerplanar Graphs}},
booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
pages = {175--186},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-92-7},
ISSN = {1868-8969},
year = {2015},
volume = {43},
editor = {Thore Husfeldt and Iyad Kanj},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5581},
URN = {urn:nbn:de:0030-drops-55815},
doi = {10.4230/LIPIcs.IPEC.2015.175},
annote = {Keywords: treewidth, monadic second order logic of graphs, finite state tree automata, k-outerplanar graphs}
}
|-short @InProceedings{JaffkeBodlaender2015,
author = {Lars Jaffke and Hans L. Bodlaender},
title = {{Definability Equals Recognizability for k-Outerplanar Graphs}},
booktitle = {IPEC '15},
pages = {175--186},
series = {LIPIcs},
year = {2015},
volume = {43}
}

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 @misc{JaffkeKwonTelle2017b,
author = {Jaffke, Lars and Kwon, O-joung and Telle, Jan Arne},
title = {A Note on the Complexity of Feedback Vertex Set Parameterized by Mim-Width},
year = {2017},
note = {arXiv:1711.05157 [cs.CC]},
}