My Research
My name is Tomáš Masařík and I am an assistant professor at the Institute of Informatics at the The Faculty of Mathematics, Informatics and Mechanics of the University of Warsaw. I participate in the project CUTACOMBS supervised by Marcin Pilipczuk.
Before, I was a postdoctoral fellow at the Simon Fraser University supervised by Bojan Mohar and Ladislav Stacho and at the University of Warsaw in the project CUTACOMBS supervised by Marcin Pilipczuk and in the project BOBR supervised by Michał Pilipczuk.
I obtained PhD at the Department of Applied Mathematics of the Faculty of Mathematics and Physics at the Charles University, Prague, Czech Republic under the supervision of Jiří Fiala. I was also affiliated with the Computer Science Institute of Charles University and I participated in the Center of Excellence - Institute for Theoretical Computer Science.
My research interests are in Graph Theory: mostly coloring problems, stuctural graph theory, algorithms, computational complexity, and parameterized complexity. A list of my publications is also presented at Google Scholar and Orcid. My preprints are usually available at arXiv.
Papers
-
Constricting the Computational Complexity Gap of the $4$-coloring Problem in $(P_t,C_3)$-free Graphs (Justyna Jaworska, Bartłomiej Kielak, TM, Jana Masaříková):
- ArXiv version.
- Cycles and Colourings 2025 (presentation - Jana Masaříková).
- General Strong Bound on the Uncrossed Number which is Tight for the Edge Crossing Number (Gaspard Charvy, TM):
- A Tight Meta-theorem for LOCAL Certification of MSO_2 Properties within Bounded Treewidth Graphs (Linda Cook, Eun Jung Kim, TM):
- Path Eccentricity and Forbidden Induced Subgraphs (Sylwia Cichacz, Claire Hilaire, TM, Jana Masaříková, Martin Milanič):
-
Unbent Collections of Orthogonal Drawings (Todor Antić, Giuseppe Liotta, TM, Giacomo Ortali, Matthias Pfretzschner, Peter Stumpf, Alexander Wolff, Johannes Zink):
- Accepted to WG 2025.
- arXiv.
- Fair Vertex Problems Parameterized by Cluster Vertex Deletion (TM, Jędrzej Olkowski, Anna Zych-Pawlewicz):
-
On the Uncrossed Number of Graphs (Martin Balko, Petr Hliněný, TM, Joachim Orthaber, Birgit Vogtenhuber, Mirko H. Wagner):
- GD 2024 (proceedings DOI).
- arXiv.
- Also presented at HOMONOLO 2024.
- Finding Diverse Solutions Parameterized by Cliquewidth (Karolina Drabik, TM):
- Proper Rainbow Saturation Numbers for Cycles (Anastasia Halfpap, Bernard Lidický, TM):
- Treewidth is Polynomial in Maximum Degree on Graphs Excluding a Planar Induced Minor (Édouard Bonnet, Jędrzej Hodor, Tuukka Korhonen, TM):
-
A Generalised Theory of Proportionality in Collective Decision Making (TM, Grzegorz Pierczyński, Piotr Skowron):
- Manuscript name: Group Fairness in Social Choice.
- EC 2024 (proceedings DOI).
- arXiv.
- Presented at Warsaw–Krakow WKRECAI 2024 (presentation).
- Minimizing an Uncrossed Collection of Drawings (Petr Hliněný, TM):
- Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time (Peter Gartland, Daniel Lokshtanov, TM, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski):
- Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic (Jesse Campion Loth, Kevin Halasz, TM, Bojan Mohar, Robert Šámal):
-
Proving a Directed Analogue of the Gyárfás-Sumner Conjecture for Orientations of P_4 (Linda Cook, TM, Marcin Pilipczuk, Amadeus Reinald, Uéverton S. Souza):
- Journal: The Electronic Journal of Combinatorics.
- arXiv.
- Presented at Dagstuhl Seminar 22481 (2022) (presentation) and at the 10th Polish Combinatorial Conference (2024).
-
On Weighted Graph Separation Problems and Flow-augmentation (Eun Jung Kim, TM, Marcin Pilipczuk, Roohani Sharma, Magnus Wahlström):
- Journal: SIAM Journal on Discrete Mathematics.
- arXiv.
- A Tight Quasi-polynomial Bound for Global Label Min-Cut (Lars Jaffke, Paloma T. Lima, TM, Marcin Pilipczuk, Uéverton S. Souza):
- Fixed-parameter Tractability of Directed Multicut with Three Terminal Pairs Parameterized by the Size of the Cutset: Twin-width Meets Flow-augmentation (Meike Hatzel, Lars Jaffke, Paloma T. Lima, TM, Marcin Pilipczuk, Roohani Sharma, Manuel Sorge):
-
Max Weight Independent Set in Graphs with no Long Claws: An Analog of the Gyárfás' Path Argument (Konrad Majewski, TM, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, Marek Sokołowski):
- ICALP 2022 (proceedings DOI).
- arXiv. Presented at UW seminar & HU Berlin 2022 (presentation).
- List Locally Surjective Homomorphisms in Hereditary Graph Classes (Pavel Dvořák, Monika Krawczyk, TM, Jana Novotná, Paweł Rzążewski, Aneta Żuk):
-
Single-conflict Colorings of Degenerate Graphs (Peter Bradshaw, TM):
- Journal: Journal of Graph Theory.
- arXiv.
- Also presented at Shanghai seminar 2021 (presentation, recording (60 min)) and at EUROCOMB 2023 (abstract DOI).
-
Linear Bounds for Cycle-free Saturation Games (Sean English, TM, Grace McCourt, Erin Meger, Michael S. Ross, Sam Spiro):
- Journal: The Electronic Journal of Combinatorics.
- arXiv. Also presented at Cycles and Colourings 2023 (presentation).
- Tuza's Conjecture for Threshold Graphs (Marthe Bonamy, Łukasz Bożyk, Andrzej Grzesik, Meike Hatzel, TM, Jana Novotná, Karolina Okrasa):
-
Robust Connectivity of Graphs on Surfaces (Peter Bradshaw, TM, Jana Novotná, Ladislav Stacho):
- Journal: SIAM Journal on Discrete Mathematics.
- EUROCOMB 2021 (proceedings DOI, presentation).
- arXiv. Also presented at CSGT 2022 (presentation).
-
Constant Congestion Brambles in Directed Graphs (TM, Marcin Pilipczuk, Paweł Rzążewski, Manuel Sorge):
- Journal: SIAM Journal on Discrete Mathematics.
- EUROCOMB 2021 (proceedings DOI, presentation).
- arXiv. Also at TU Berlin seminar 2021 (presentation).
-
Random 2-Cell Embeddings of Multistars (Jesse Campion Loth, Kevin Halasz, TM, Bojan Mohar, Robert Šámal):
- Journal: Proceedings of the AMS.
- EUROCOMB 2021 (proceedings DOI).
- arXiv.
-
The Phase Transition of Discrepancy in Random Hypergraphs (Calum MacRury, TM, Leilani Pai, Xavier Pérez-Giménez):
- Journal: SIAM Journal on Discrete Mathematics.
- arXiv.
-
Note on 3-Coloring of (2P_4, C_5)-Free Graphs (Vít Jelínek, Tereza Klimošová, TM, Jana Novotná, Aneta Pokorná):
- Journal: Algorithmica.
- WG 2021 (proceedings DOI, presentation, recording (25 min)).
- arXiv.
-
On Weak Flexibility in Planar Graphs (Bernard Lidický, TM, Kyle Murphy, Shira Zerbib):
- Journal: Graphs and Combinatorics.
- arXiv.
-
Flexible List Colorings in Graphs with Special Degeneracy Conditions (Peter Bradshaw, TM, Ladislav Stacho):
- Journal: Journal of Graph Theory.
- ISAAC 2020 (proceedings DOI).
- arXiv.
- Also presented at SIAM DM 2021, SFU Discrete Math 2021 (recording 50 min), and UW algorithms seminar 2021 (presentation, recording 50 min).
-
Clique-Width: Harnessing the Power of Atoms (Konrad Dabrowski, TM, Jana Novotná, Daniël Paulusma, Paweł Rzążewski):
- Journal: Journal of Graph Theory.
- WG 2020 (proceedings DOI).
- arXiv. Also at Haifa workshop 2020 (presentation).
-
Flexibility of Planar Graphs – Sharpening the Tools to Get Lists of Size Four (Ilkyoo Choi, Felix C. Clemen, Michael Ferrara, Paul Horn, Fuhong Ma, TM):
- Journal: Discrete Applied Mathematics.
- arXiv. Also at JMM 2020 (presentation).
-
Optimal Discretization is Fixed-parameter Tractable (Stefan Kratsch, TM, Irene Muzi, Marcin Pilipczuk, Manuel Sorge):
- SODA 2021 (proceedings DOI).
- arXiv. SFU Discrete Math 2021 (presentation, recording 50 min); Frontiers of Parameterized Complexity (recording 70 min).
-
U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited (Jiří Kratochvíl, TM, Jana Novotná):
- Journal: Algorithmica.
- MFCS 2020 (proceedings DOI; recording 20 min).
- arXiv.
- Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View (Radoslav Hušek, Dušan Knop, TM):
-
Jones' Conjecture in Subcubic Graphs (Marthe Bonamy, François Dross, TM, Andrea Munaro, Wojciech Nadara, Marcin Pilipczuk, Michał Pilipczuk):
- Journal: The Electronic Journal of Combinatorics.
- arXiv.
-
FPT Algorithms for Diverse Collections of Hitting Sets (Julien Baste, Lars Jaffke, TM, Geevarghese Philip, Günter Rote):
- Journal: Algorithms (Special Issue).
- arXiv.
-
Packing Directed Circuits Quarter- and Half-Integrally (TM, Irene Muzi, Marcin Pilipczuk, Paweł Rzążewski, Manuel Sorge):
- Journal: Combinatorica.
- ESA 2019 (proceedings DOI; presentation).
- arXiv. Also at Cycles and Colourings 2019 and Iowa State (2020, recording 35 min).
-
Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory (Julien Baste, Michael R. Fellows, Lars Jaffke, TM, Mateus de Oliveira Oliveira, Geevarghese Philip, Frances A. Rosamond):
- Journal: Artificial Intelligence.
- IJCAI 2020 (proceedings DOI; recording 5 min, talk 15 min, poster).
- arXiv.
-
Flexibility of planar graphs without 4-cycles (TM): [PDF]
- EUROCOMB 2019 (proceedings, presentation).
- arXiv.
- Also at DIMEA days 2019 (poster).
-
Flexibility of planar graphs of girth at least six (Zdeněk Dvořák, TM, Jan Musílek, Ondřej Pangrác):
[PDF]
- Journal: Journal of Graph Theory.
- arXiv.
- Also at DIMEA days 2019 (poster).
-
Flexibility of triangle-free planar graphs (Zdeněk Dvořák, TM, Jan Musílek, Ondřej Pangrác):
- Journal: Journal of Graph Theory.
- arXiv.
- Also at Cycles and Colourings 2017 (presentation) and DIMEA days 2019 (poster).
-
Steiner Tree Heuristics [PACE 2018 TRACK C] (Radoslav Hušek, Tomáš Toufar, Dušan Knop, TM, Eduard Eiben): [PDF]
- PACE report 2018.
- IPEC ceremony results: 4th place.
- Public repository.
- Ranking on public instances.
-
Colouring (P_r+P_s)-Free Graphs (Tereza Klimošová, Josef Malík, TM, Jana Novotná, Daniël Paulusma, Veronika Slívová):
- Journal: Algorithmica.
- ISAAC 2018 (proceedings DOI; presentation).
- arXiv. Also ALGO seminar (Bergen, 2018, slides); Noon lecture (Charles University, 2018, slides).
-
Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices (Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop, TM, Tomáš Toufar, Pavel Veselý):
- Journal: SIAM Journal on Discrete Mathematics.
- STACS 2018 (proceedings DOI; presentation).
- arXiv. Also PAAW 2018 (presentation); HALG 2018 (poster).
-
On difference graphs and the local dimension of posets (Jinha Kim, Ryan R. Martin, TM, Warren Shull, Heather C. Smith, Andrew Uzzell, Zhiyu Wang):
- Journal: European Journal of Combinatorics.
- arXiv. Also Noon lecture (Prague, 2018) and ALGO seminar (Bergen, 2018, slides); HOMONOLO 2017.
-
Notes on complexity of packing coloring (Minki Kim, Bernard Lidický, TM, Florian Pfender):
- Journal: Information Processing Letters.
- arXiv. Also Warsaw University of Technology seminar; Cycles and Colourings 2018 (presentation).
- Duality gap in interval linear programming (Jana Novotná, Milan Hladík, TM):
-
Parameterized Complexity of Fair Vertex Evaluation Problems (Dušan Knop, TM, Tomáš Toufar): [PDF]
- MFCS 2019 (proceedings DOI; presentation).
- arXiv. Also CSGT 2017 (slides); MCGTC 2017; GROW 2017 (slides); ISAAC 2018 open problems (slides).
-
Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity (Dušan Knop, Martin Koutecký, TM, Tomáš Toufar):
- Journal: Logical Methods in Computer Science.
- WG 2017 (proceedings DOI; presentation).
- arXiv. Also at MCW XXII (2017).
-
Parameterized complexity of fair deletion problems (TM, Tomáš Toufar):
- Journal: Discrete Applied Mathematics.
- TAMC 2017 (proceedings DOI; presentation).
- arXiv. Also BGW 2016 (slides); MEMICS 2016 (poster).
-
Anti-Path Cover on Sparse Graph Classes (Pavel Dvořák, Dušan Knop, TM):
- MEMICS 2016 (proceedings DOI; presentation).
- arXiv. Also BGW 2016 (presentation).
-
Triangle-free planar graphs with the smallest independence number (Zdeněk Dvořák, TM, Jan Musílek, Ondřej Pangrác):
- Journal: Journal of Graph Theory.
- arXiv. Also Cycles and Colourings 2016 (presentation).
-
Computational complexity of Distance Edge labeling (Dušan Knop, TM):
- Journal: Discrete Applied Mathematics.
- IWOCA 2015 (proceedings DOI; presentation).
- arXiv. Noon lecture (Prague, 2015).
- A pre-printed ITI-series version. Diploma Thesis (2014, CZ).
Internships / Research Collaboration
- IT University of Copenhagen, Danemark, may 2023 (P. Lima)
- Postdoc University of Warsaw, Poland aug 2021 - feb 2022 (Mi. Pilipczuk, project BOBR)
- Postdoc Simon fraser University, Canada feb 2020 - aug 2021 (B. Mohar and L. Stacho)
- Iowa State University, USA jan 2020 (B. Lidický)
- Postdoc University of Warsaw, Poland oct 2019 - jan 2020 (Ma. Pilipczuk, project CUTACOMBS)
- Kansas University, USA jul 2019 (GRWC)
- University of Warsaw, Poland sep 2018 - sep 2019 (Ma. Pilipczuk, project CUTACOMBS)
- Durham University, UK nov 2018, apr-may 2019 (D. Paulusma)
- Warsaw University of Technology, Poland nov 2018
- University of Bergen, Norway jan-jul 2018 (Erasmus)
- LAMSADE, Université Paris-Dauphine, France dec 2017
- University of Denver, Colorado and University of Colorado Denver, USA jul 2017 (GRWC)
- DIMACS, Rutgers, The State University of New Jersey, US jun-jul 2015 (REU)
- Department of Computer and Information Science, University of Oregon, US apr 2015
- Grenoble Alpes University - Laboratory G-SCOP, France dec 2014
Organization
- ICALP 2018
- CSGT 2017
- Spring School 2014, 2016, 2017, 2018, 2019
- Homonolo 2015, 2016, 2017, 2018, 2019, 2021
Other (reports, ed.)
- Spring School 2018 printed in ITI-series.
- Czech-Slovak conference on Graph Theory 2017 printed in ITI-series.
- Spring School 2017 printed in ITI-series.
- Spring School 2016 printed in ITI-series.
- The report from REU 2015 printed in ITI-series.
PhD Thesis
- PhD Thesis 2019 at Charles University. [PDF]
- Extended astract of PhD Thesis at Charles University. [PDF]
masarik<a>mimuw.edu.pl
CENT building room 03.111, MIMUW, Banacha 2, Warsaw, 02-097, Poland
Room 1650, MIMUW, Banacha 2, Warsaw, 02-097, Poland
Room 8514, Department of Mathematics, Simon Fraser university, 8888 University Drive, Burnaby, V5A 1S6, Canada
Room 320, KAM MFF, Malostranské náměstí 25, Praha 1, 11800, Czech Republic