Tomáš Masařík

Dr. Tomáš Masařík

University of Warsaw
orcid

Research Focus & Metrics

Academic Career Length

12Years (2015-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 February 2022 in Artificial Intelligence
Verified
Journal Article
Closed access
JBJulien Baste
Julien Baste
MFMichael R. Fellows
Michael R. Fellows
LJLars Jaffke
Lars Jaffke
TMTomáš Masařík
Tomáš Masařík
MOMateus de Oliveira Oliveira
Mateus de Oliveira Oliveira
Frances  RosamondFrances Rosamond
Frances Rosamond

27 November 2019 in Algorithms
Verified
Journal Article
Open access
PDF file
JBJulien Baste
Julien Baste
LJLars Jaffke
Lars Jaffke
TMTomáš Masařík
Tomáš Masařík
GPGeevarghese Philip
Geevarghese Philip
GRGünter Rote
Günter Rote
In this work, we study the d-Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of r solutions of size at most k each, which has recently been introduced to the field of parameterized complexity. This paradigm is aimed at addressing the loss of important side information which typically occurs during the abstraction process that models real-world problems as computational problems. We use two measures for the diversity of such a collection: the sum of all pairwise Hamming distances, and the minimum pairwise Hamming distance. We show that both problems are fixed-parameter tractable in k + r for both diversity measures. A key ingredient in our algorithms is a (problem independent) network flow formulation that, given a set of ‘base’ solutions, computes a maximally diverse collection of solutions. We believe that this could be of independent interest.


4 December 2019 in Logical Methods in Computer Science
Verified
Journal Article
Open access
PDF file
DKDušan Knop
Dušan Knop
MKMartin Koutecký
Martin Koutecký
TMTomáš Masařík
Tomáš Masařík
TTTomáš Toufar
Tomáš Toufar
This paper settles the computational complexity of model checking of several extensions of the monadic second order (MSO) logic on two classes of graphs: graphs of bounded treewidth and graphs of bounded neighborhood diversity. A classical theorem of Courcelle states that any graph property definable in MSO is decidable in linear time on graphs of bounded treewidth. Algorithmic metatheorems like Courcelle's serve to generalize known positive results on various graph classes. We explore and extend three previously studied MSO extensions: global and local cardinality constraints (CardMSO and MSO-LCC) and optimizing the fair objective function (fairMSO). First, we show how these extensions of MSO relate to each other in their expressive power. Furthermore, we highlight a certain "linearity" of some of the newly introduced extensions which turns out to play an important role. Second, we provide parameterized algorithm for the aforementioned structural parameters. On the side of neighborhood diversity, we show that combining the linear variants of local and global cardinality constraints is possible while keeping the linear (FPT) runtime but removing linearity of either makes this impossible. Moreover, we provide a polynomial time (XP) algorithm for the most powerful of studied extensions, i.e. the combination of global and local constraints. Furthermore, we show a polynomial time (XP) algorithm on graphs of bounded treewidth for the same extension. In addition, we propose a general procedure of deriving XP algorithms on graphs on bounded treewidth via formulation as Constraint Satisfaction Problems (CSP). This shows an alternate approach as compared to standard dynamic programming formulations.Comment: An extended abstract appeared in Proceedings of WG 2017

1 May 2020 in European Journal of Combinatorics
Verified
Journal Article
Closed access
JKJinha Kim
Jinha Kim
RMRyan R. Martin
Ryan R. Martin
TMTomáš Masařík
Tomáš Masařík
WSWarren Shull
Warren Shull
HSHeather C. Smith
Heather C. Smith
ZWZhiyu Wang
Zhiyu Wang

25 January 2020 in Algorithmica
Verified
Journal Article
Open access
PDF file
TKTereza Klimošová
Tereza Klimošová
JMJosef Malík
Josef Malík
TMTomáš Masařík
Tomáš Masařík
JNJana Novotná
Jana Novotná
DPDaniël Paulusma
Daniël Paulusma
VSVeronika Slívová
Veronika Slívová
The k-Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a fixed integer k such that no two adjacent vertices are coloured alike. If each vertex u must be assigned a colour from a prescribed list $$L(u)\subseteq \{1,\ldots ,k\},$$ L ( u ) ⊆ { 1 , … , k } , then we obtain the List k-Colouring problem. A graph G is H-free if G does not contain H as an induced subgraph. We continue an extensive study into the complexity of these two problems for H-free graphs. The graph $$P_r+P_s$$ P r + P s is the disjoint union of the r-vertex path $$P_r$$ P r and the s-vertex path $$P_s.$$ P s . We prove that List 3-Colouring is polynomial-time solvable for $$(P_2+P_5)$$ ( P 2 + P 5 ) -free graphs and for $$(P_3+P_4)$$ ( P 3 + P 4 ) -free graphs. Combining our results with known results yields complete complexity classifications of 3-Colouring and List 3-Colouring on H-free graphs for all graphs H up to seven vertices.