Tomáš Toufar

Tomáš Toufar

Auto-generated profile, based on publicly available information

Tomáš Toufar

Computer Science Institute Charles University Prague Czech Republic

Research Focus & Metrics

Academic Career Length

14Years (2013-Present)

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

Representative Publications

View All Publications

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 January 2021 in SIAM Journal on Discrete Mathematics
Verified
Journal Article
Closed access
PDPavel Dvořák
Pavel Dvořák
AFAndreas E. Feldmann
Andreas E. Feldmann
DKDušan Knop
Dušan Knop
TMTomáš Masařík
Tomáš Masařík
TTTomáš Toufar
Tomáš Toufar
PVPavel Veselý
Pavel Veselý
We study the Steiner Tree problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensively studied from t...

21 March 2017
Verified
Book Chapter
Closed access
PDF file
TMTomáš Masařík
Tomáš Masařík
TTTomáš Toufar
Tomáš Toufar

14 August 2020 in arXiv
Verified
Preprint
Open access
PDF file
PDPavel Dvořák
Pavel Dvořák
DKDušan Knop
Dušan Knop
TTTomáš Toufar
Tomáš Toufar
In this paper, we study the Target Set Selection problem from a parameterized complexity perspective. Here for a given graph and a threshold for each vertex, the task is to find a set of vertices (called a target set) which activates the whole graph during the following iterative process. A vertex outside the active set becomes active if the number of so far activated vertices in its neighborhood is at least its threshold. We give two parameterized algorithms for a special case where each vertex has the threshold set to the half of its neighbors (the so-called Majority Target Set Selection problem) for parameterizations by the neighborhood diversity and the twin cover number of the input graph. We complement these results from the negative side. We give a hardness proof for the Majority Target Set Selection problem when parameterized by (a restriction of) the modular-width - a natural generalization of both previous structural parameters. We also show the Target Set Selection problem parameterized by the neighborhood diversity or by the twin cover number is W[1]-hard when there is no restriction on the thresholds.

1 January 2013 in Lecture Notes in Computer Science
Verified
Book Chapter
Closed access
PDF file
LMLukáš Mach
Lukáš Mach
TTTomáš Toufar
Tomáš Toufar