Publications

Structural Parameterizations of b-Coloring
with Paloma T. Lima and Roohani Sharma
ISAAC 2023 | pdf | bibtex

Dynamic Programming on Bipartite Tree Decompositions
with Laure Morelle, Ignasi Sau, and Dimitrios M. Thilikos
IPEC 2023 | bibtex | arXiv

Treewidth is NP-Complete on Cubic Graphs
with Hans L. Bodlaender, Édouard Bonnet, Dušan Knop, Paloma T. Lima, Martin Milanič, Sebastian Ordyniak, Sukanya Pandey, and Ondřej Suchý
IPEC 2023 | bibtex | arXiv

A logic-based algorithmic meta-theorem for mim-width
with Benjamin Bergougnoux and Jan Dreier
SODA 2023 | HIGHLIGHTS 2022 | arXiv | poster | bibtex

Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
with Meike Hatzel, Paloma T. Lima, Tomáš Masařík, Marcin Pilipczuk, Roohani Sharma, and Manuel Sorge
SODA 2023 | HALG 2023 | arXiv | bibtex

A tight quasi-polynomial bound for Global Label Min-Cut
with Paloma T. Lima, Tomáš Masařík, Marcin Pilipczuk, and Uéverton S. Souza
SODA 2023 | arXiv | bibtex

On the hardness of generalized domination problems parameterized by mim-width
with Brage I. K. Bakkane
IPEC 2022 | bibtex

A Unifying Framework for Characterizing and Computing Width Measures
with Eduard Eiben, Robert Ganian, Thekla Hamm, and O-joung Kwon
ITCS 2022 | arXiv | bibtex

Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach
with Mateus de Oliveira Oliveira and Hans Raj Tiwary
MFCS 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 | arXiv | bibtex

XNLP-completeness for Parameterized Problems on Graphs with a Linear Structure
with Hans L. Bodlaender, Carla Groenland, Hugo Jacob, and Paloma T. Lima
Algorithmica (accepted, 2024) | Special Issue: IPEC 2022 | best paper award at IPEC 2022 | arXiv | bibtex

Taming graphs with no large creatures and skinny ladders
with Jakub Gajarský, Paloma T. Lima, Jana Masaříková, Marcin Pilipczuk, Paweł Rzążewski, and Uéverton S. Souza
SIAM J. Discrete Math. (accepted, 2024) | ESA 2022 | arXiv | bibtex

Diverse Pairs of Matchings
with Fedor V. Fomin, Petr A. Golovach, Geevarghese Philip, and Danil Sagunov
Algorithmica (2024) | ISAAC 2020 | pdf | arXiv | bibtex

Classes of intersection digraphs with good algorithmic properties
with O-joung Kwon and Jan Arne Telle
J. Graph Theory (2024) | STACS 2022 | arXiv | bibtex

b-Coloring Parameterized by Clique-Width
with Paloma T. Lima and Daniel Lokshtanov
Theory Comput. Syst. (2024) | Special Issue: STACS 2021 | STACS 2021 | pdf | bibtex

On the maximum number of edges in planar graphs of bounded degree and matching number
with Paloma T. Lima
Discrete Math. (2023) | arXiv | bibtex

Typical Sequences Revisited - Computing Width Parameters of Graphs
with Hans L. Bodlaender and Jan Arne Telle
Theory Comput. Syst. (2023) | Special Issue: STACS 2020 | STACS 2020 | pdf | bibtex

Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
with Bart M. P. Jansen
Discrete Appl. Math. (2023) | CIAC 2017 | arXiv | bibtex

Well-partitioned chordal graphs
with Jungho Ahn, O-joung Kwon, and Paloma T. Lima
Discrete Math. (2022) | WG 2020 | CIAC 2021 | bibtex

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
Artif. Intell. (2022) | IJCAI 2020 | pdf | bibtex

Structural Parameterizations of Clique Coloring
with Paloma T. Lima and Geevarghese Philip
Algorithmica (2022) | MFCS 2020 | arXiv | bibtex

Mim-Width I. Induced Path Problems
with O-joung Kwon and Jan Arne Telle
Discrete Appl. Math. (2020) | IPEC 2017 | bibtex

A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs
with Paloma T. Lima
Theoret. Comput. Sci. (2020) | MFCS 2019 | 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
Theoret. Comput. Sci. (2019) | IPEC 2018 | bibtex

FPT Algorithms for Diverse Collections of Hitting Sets
with Julien Baste, Tomáš Masařík, Geevarghese Philip, and Günter Rote
Algorithms (2019) | bibtex

What Is Known About Vertex Cover Kernelization?
with Michael R. Fellows, Aliz Izabella Király, Frances A. Rosamond, and Mathias Weller
LNCS 2018 | arXiv | bibtex
Note: The arXiv-version fixes a flaw in Reduction R.8 of the LNCS-version

On Weak Isomorphism of Rooted Vertex-Colored Graphs
with Mateus de Oliveira Oliveira
WG 2018 | bibtex

Recognizability Equals Definability for k-Outerplanar Graphs and l-Chordal Partial k-Trees
with Hans L. Bodlaender, Pinar Heggernes, and Jan Arne Telle
Eur. J. Combin. (2017) | IPEC 2015 | bibtex
Note: Contains results from another extended abstract that appeared at EUROCOMB 2015.