29 citations · 212 across the 50 of their papers we have counts for
50 papers
Edge-decomposition into Two Triangular Forests is NP-complete
Beniamin Bibrowski, Tomáš Masařík
Let be a graph class that is closed under topological minors and 1-sums, has decidable membership, contains a triangle, and is not the class of all graphs. Recently, L…
Separator Theorem for Minor-Free Graphs in Linear Time
Édouard Bonnet, Tuukka Korhonen, Hung Le +2
The planar separator theorem by Lipton and Tarjan [FOCS '77, SIAM Journal on Applied Mathematics '79] states that any planar graph with vertices has a balanced separator of siz…
Constricting the Computational Complexity Gap of the -Coloring Problem in -free Graphs
Justyna Jaworska, Bartłomiej Kielak, Tomáš Masařík +1
The -Coloring problem on hereditary graph classes has been a deeply researched problem over the last decade. A hereditary graph class is characterized by a (possibly infinite) l…
A Tight Meta-theorem for LOCAL Certification of MSO Properties within Bounded Treewidth Graphs
Linda Cook, Eun Jung Kim, Tomáš Masařík
Distributed networks are prone to errors so verifying their output is critical. Hence, we develop LOCAL certification protocols for graph properties in which nodes are given certif…
Path Eccentricity and Forbidden Induced Subgraphs
Sylwia Cichacz, Claire Hilaire, Tomáš Masařík +2
The path eccentricity of a connected graph is the minimum integer such that has a path such that every vertex is at distance at most from the path. A result of Duff…
Unbent Collections of Orthogonal Drawings
Todor Antić, Giuseppe Liotta, Tomáš Masařík +5
Recently, there has been interest in representing single graphs by multiple drawings; for example, using graph stories, storyplans, or uncrossed collections. In this paper, we appl…
Fair Vertex Problems Parameterized by Cluster Vertex Deletion
Tomáš Masařík, Jędrzej Olkowski, Anna Zych-Pawlewicz
In this paper we study fair variants of MSO definable problems parameterized by cluster vertex deletion number, i.e., the smallest number of vertices required to be removed fro…
Finding Diverse Solutions Parameterized by Cliquewidth
Karolina Drabik, Tomáš Masařík
Finding a few solutions for a given problem that are diverse, as opposed to finding a single best solution to solve the problem, has recently become a notable topic in theoretical…
Proper Rainbow Saturation Numbers for Cycles
Anastasia Halfpap, Bernard Lidický, Tomáš Masařík
We say that an edge-coloring of a graph is proper if every pair of incident edges receive distinct colors, and is rainbow if no two edges of receive the same color. Further…
A Generalised Theory of Proportionality in Collective Decision Making
Tomáš Masařík, Grzegorz Pierczyński, Piotr Skowron
We consider a voting model, where a number of candidates need to be selected subject to certain feasibility constraints. The model generalises committee elections (where there is a…
Minimizing an Uncrossed Collection of Drawings
Petr Hliněný, Tomáš Masařík
In this paper, we introduce the following new concept in graph drawing. Our task is to find a small collection of drawings such that they all together satisfy some property that is…
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
Peter Gartland, Daniel Lokshtanov, Tomáš Masařík +3
We show that the Maximum Weight Independent Set problem (MWIS) can be solved in quasi-polynomial time on -free graphs (graphs excluding a fixed graph as an induced subgraph)…
Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic
Jesse Campion Loth, Kevin Halasz, Tomáš Masařík +2
A random 2-cell embedding of a connected graph in some orientable surface is obtained by choosing a random local rotation around each vertex. Under this setup, the number of fa…
Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of
Linda Cook, Tomáš Masařík, Marcin Pilipczuk +2
An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph is -free if does not contain as an induced sub(di)graph. The…
On weighted graph separation problems and flow-augmentation
Eun Jung Kim, Tomáš Masařík, Marcin Pilipczuk +2
One of the first application of the recently introduced technique of \emph{flow-augmentation} [Kim et al., STOC 2022] is a fixed-parameter algorithm for the weighted version of \te…
A tight quasi-polynomial bound for Global Label Min-Cut
Lars Jaffke, Paloma T. Lima, Tomáš Masařík +2
We study a generalization of the classic Global Min-Cut problem, called Global Label Min-Cut (or sometimes Global Hedge Min-Cut): the edges of the input (multi)graph are labeled (o…
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 +4
We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph , pairs of ve…
Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
Konrad Majewski, Tomáš Masařík, Jana Novotná +4
We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw as an induced subgraph [Chudnovsky, Pilipczuk, Pilip…
List Locally Surjective Homomorphisms in Hereditary Graph Classes
Pavel Dvořák, Monika Krawczyk, Tomáš Masařík +3
A locally surjective homomorphism from a graph to a graph is an edge-preserving mapping from to that is surjective in the neighborhood of each vertex in .…
Single-conflict colorings of degenerate graphs
Peter Bradshaw, Tomáš Masařík
We consider the single-conflict coloring problem, a graph coloring problem in which each edge of a graph receives a forbidden ordered color pair. The task is to find a vertex color…
Tuza's Conjecture for Threshold Graphs
Marthe Bonamy, Łukasz Bożyk, Andrzej Grzesik +4
Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds…
Robust Connectivity of Graphs on Surfaces
Peter Bradshaw, Tomáš Masařík, Jana Novotná +1
Let denote the set of leaves in a tree . One natural problem is to look for a spanning tree of a given graph such that is as large as possible. This proble…
Constant congestion brambles in directed graphs
Tomáš Masařík, Marcin Pilipczuk, Paweł Rzążewski +1
The Directed Grid Theorem, stating that there is a function such that a directed graphs of directed treewidth at least contains a directed grid of size at least as a…
Random 2-cell embeddings of multistars
Jesse Campion Loth, Kevin Halasz, Tomáš Masařík +2
Random 2-cell embeddings of a given graph are obtained by choosing a random local rotation around every vertex. We analyze the expected number of faces, , of s…