29 citations · 212 across the 50 of their papers we have counts for
17 papers · 1 filter
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…
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…
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)…
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 .…
Optimal Discretization is Fixed-parameter Tractable
Stefan Kratsch, Tomáš Masařík, Irene Muzi +2
Given two disjoint sets and of points in the plane, the Optimal Discretization problem asks for the minimum size of a family of horizontal and vertical lines that separ…
Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View
Radek Hušek, Dušan Knop, Tomáš Masařík
In the Steiner Tree problem we are given an edge weighted undirected graph and a set of terminals . The task is to find a connected subgraph of conta…
U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
Jan Kratochvíl, Tomáš Masařík, Jana Novotná
Interval graphs, intersection graphs of segments on a real line (intervals), play a key role in the study of algorithms and special structural properties. Unit interval graphs, the…
FPT Algorithms for Diverse Collections of Hitting Sets
Julien Baste, Lars Jaffke, Tomáš Masařík +2
In this work, we study the -Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of solutions of size at most each, which has…
Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
Julien Baste, Michael R. Fellows, Lars Jaffke +4
When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instanc…
Colouring -Free Graphs
Tereza Klimošová, Josef Malík, Tomáš Masařík +3
The -Colouring problem is to decide if the vertices of a graph can be coloured with at most colours for a fixed integer such that no two adjacent vertices are coloured a…
Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop +3
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 extensive…
Anti-Path Cover on Sparse Graph Classes
Pavel Dvořák, Dušan Knop, Tomáš Masařík
We show that it is possible to use Bondy-Chvatal closure to design an FPT algorithm that decides whether or not it is possible to cover vertices of an input graph by at most k vert…