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

  1. On the Uncrossed Number of Graphs (M. Balko, P. Hliněný, TM, J. Orthaber, B. Vogtenhuber, M.H. Wagner):
  2. Finding Diverse Solutions Parameterized by Cliquewidth (K. Drabik, TM):
  3. Proper Rainbow Saturation Numbers for Cycles (A. Halfpap, B. Lidický, TM):
  4. Treewidth is Polynomial in Maximum Degree on Graphs Excluding a Planar Induced Minor (É. Bonnet, J. Hodor, T. Korhonen, TM):
  5. A Generalised Theory of Proportionality in Collective Decision Making (TM, G. Pierczyński, P. Skowron):
  6. Minimizing an Uncrossed Collection of Drawings (P. Hliněný, TM):
  7. Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time (P. Gartland, D. Lokshtanov, TM, Ma. Pilipczuk, Mi. Pilipczuk, P. Rzążewski):
  8. Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic (J. Campion Loth, K. Halasz, TM, B. Mohar, R. Šámal):
  9. Proving a Directed Analogue of the Gyárfás-Sumner Conjecture for Orientations of P_4 (L. Cook, TM, Ma. Pilipczuk, A. Reinald, U.S. Souza):
  10. On Weighted Graph Separation Problems and Flow-augmentation (E.J. Kim, TM, Ma. Pilipczuk, R. Sharma, M. Wahlström):
  11. A Tight Quasi-polynomial Bound for Global Label Min-Cut (L. Jaffke, P.T. Lima, TM, Ma. Pilipczuk, U.S. Souza):
  12. Fixed-parameter Tractability of Directed Multicut with Three Terminal Pairs Parameterized by the Size of the Cutset: Twin-width Meets Flow-augmentation (M. Hatzel, L. Jaffke, P.T. Lima, TM, Ma. Pilipczuk, R. Sharma, M. Sorge):
  13. Max Weight Independent Set in Graphs with no Long Claws: An Analog of the Gyárfás' Path Argument (K. Majewski, TM, J. Novotná, K. Okrasa, Ma. Pilipczuk, P. Rzążewski, M. Sokołowski):
  14. List Locally Surjective Homomorphisms in Hereditary Graph Classes (P. Dvořák, M. Krawczyk, TM, J. Novotná, P. Rzążewski, A. Żuk):
  15. Single-conflict Colorings of Degenerate Graphs (P. Bradshaw, TM):
  16. Linear Bounds for Cycle-free Saturation Games (S. English, TM, G. McCourt, E. Meger, M.S. Ross, S. Spiro):
  17. Tuza's Conjecture for Threshold Graphs (M. Bonamy, Ł. Bożyk, A. Grzesik, M. Hatzel, TM, J. Novotná, K. Okrasa):
  18. Robust Connectivity of Graphs on Surfaces (P. Bradshaw, TM, J. Novotná, L. Stacho):
  19. Constant Congestion Brambles in Directed Graphs (TM, Ma. Pilipczuk, P. Rzążewski, M. Sorge):
  20. Random 2-Cell Embeddings of Multistars (J. Campion Loth, K. Halasz, TM, B. Mohar, R. Šámal):
  21. The Phase Transition of Discrepancy in Random Hypergraphs (C. MacRury, TM, L. Pai, X. Pérez-Giménez):
  22. Note on 3-Coloring of (2P_4,C_5)-Free Graphs (V. Jelínek, T. Klimošová, TM, J. Novotná, A. Pokorná):
  23. On Weak Flexibility in Planar Graphs (B. Lidický, TM, K. Murphy, S. Zerbib):
  24. Flexible List Colorings in Graphs with Special Degeneracy Conditions (P. Bradshaw, TM, L. Stacho):
  25. Clique-Width: Harnessing the Power of Atoms (K. Dabrowski, TM, J. Novotná, D. Paulusma, P. Rzążewski):
  26. Flexibility of Planar Graphs – Sharpening the Tools to Get Lists of Size Four (I. Choi, F.C. Clemen, M. Ferrara, P. Horn, F. Ma, TM):
  27. Optimal Discretization is Fixed-parameter Tractable (S. Kratsch, TM, I. Muzi, Ma. Pilipczuk, M. Sorge):
  28. U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited (J. Kratochvíl, TM, J. Novotná):
  29. Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View (R. Hušek, D. Knop, TM):
  30. Jones' Conjecture in subcubic graphs (M. Bonamy, F. Dross, TM, W. Nadara, Ma. Pilipczuk, Mi. Pilipczuk):
  31. FPT Algorithms for Diverse Collections of Hitting Sets (J. Baste, L. Jaffke, TM, G. Philip, G. Rote):
  32. Packing Directed Circuits Quarter- and Half-Integrally (TM, I. Muzi, Ma. Pilipczuk, P. Rzążewski, M. Sorge):
  33. Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory (J. Baste, M.R. Fellows, L. Jaffke, TM, M. de Oliveira Oliveira, G. Philip, F.A. Rosamond):
  34. Flexibility of planar graphs without 4-cycles (TM): [PDF]
  35. Flexibility of planar graphs of girth at least six (Z. Dvořák, TM, J. Musílek, O. Pangrác): [PDF]
  36. Flexibility of triangle-free planar graphs (Z. Dvořák, TM, J. Musílek, O. Pangrác):
  37. Steiner Tree Heuristics [PACE 2018 TRACK C] (R. Hušek, T. Toufar, D. Knop, TM, E. Eiben): [PDF]
  38. Colouring (P_r+P_s)-Free Graphs (T. Klimošová, J. Malík, TM, J. Novotná, D. Paulusma, V. Slívová):
  39. Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices (P. Dvořák, A.E. Feldmann, D. Knop, TM, T. Toufar, P. Veselý):
  40. On difference graphs and the local dimension of posets (J. Kim, R.R. Martin, TM, W. Shull, H.C. Smith, A. Uzzell, Z. Wang):
  41. Notes on complexity of packing coloring (M. Kim, B. Lidický, TM, F. Pfender):
  42. Duality gap in interval linear programming (J. Novotná, M. Hladík, TM):
  43. Parameterized Complexity of Fair Vertex Evaluation Problems (D. Knop, TM, T. Toufar): [PDF]
  44. Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity (D. Knop, M. Koutecký, TM, T. Toufar):
  45. Parameterized complexity of fair deletion problems (TM, T. Toufar):
  46. Anti-Path Cover on Sparse Graph Classes (P. Dvořák, D. Knop, TM):
  47. Triangle-free planar graphs with the smallest independence number (Z. Dvořak, TM, J. Musílek, O. Pangrác):
  48. Computational complexity of Distance Edge labeling (D. Knop, TM):

Internships / Research Collaboration

Organization

Other (reports, ed.)

  1. Spring School 2018 printed in ITI-series.
  2. Czech-Slovak conference on Graph Theory 2017 printed in ITI-series.
  3. Spring School 2017 printed in ITI-series.
  4. Spring School 2016 printed in ITI-series.
  5. The report from REU 2015 printed in ITI-series.

PhD Thesis

  1. PhD Thesis 2019 at Charles University. [PDF]
  2. 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