16 citations · 188 across the 122 of their papers we have counts for
9 papers · 1 filter
Strong immersion is a well-quasi-ordering for semi-complete digraphs
Florian Barbero, Christophe Paul, Michal Pilipczuk
We prove that the strong immersion order is a well-quasi-ordering on the class of semi-complete digraphs, thereby strengthening a result of Chudnovsky and Seymour that this holds f…
Polynomial-time algorithm for Maximum Weight Independent Set on -free graphs
Andrzej Grzesik, Tereza Klimošová, Marcin Pilipczuk +1
In the classic Maximum Weight Independent Set problem we are given a graph with a nonnegative weight function on vertices, and the goal is to find an independent set in of…
A subexponential parameterized algorithm for Directed Subset Traveling Salesman Problem on planar graphs
Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk
There are numerous examples of the so-called ``square root phenomenon'' in the field of parameterized algorithms: many of the most fundamental graph problems, parameterized by some…
On Directed Feedback Vertex Set parameterized by treewidth
Marthe Bonamy, Łukasz Kowalik, Jesper Nederlof +3
We study the Directed Feedback Vertex Set problem parameterized by the treewidth of the input graph. We prove that unless the Exponential Time Hypothesis fails, the problem cannot…
Exploring the complexity of layout parameters in tournaments and semi-complete digraphs
Florian Barbero, Christophe Paul, Michał Pilipczuk
A simple digraph is semi-complete if for any two of its vertices and , at least one of the arcs and is present. We study the complexity of computing two layo…
On the number of types in sparse graphs
Michał Pilipczuk, Sebastian Siebertz, Szymon Toruńczyk
We prove that for every class of graphs which is nowhere dense, as defined by Nesetril and Ossona de Mendez, and for every first order formula , whe…
On low rank-width colorings
O-joung Kwon, Michał Pilipczuk, Sebastian Siebertz
We introduce the concept of low rank-width colorings, generalising the notion of low tree-depth colorings introduced by Nešetřil and Ossona de Mendez in [Grad and classes with boun…
Model-Checking for Successor-Invariant First-Order Formulas on Graph Classes of Bounded Expansion
Jan van den Heuvel, Stephan Kreutzer, Michał Pilipczuk +3
A successor-invariant first-order formula is a formula that has access to an auxiliary successor relation on a structure's universe, but the model relation is independent of the pa…
Optimizing tree decompositions in MSO
Mikołaj Bojańczyk, Michał Pilipczuk
The classic algorithm of Bodlaender and Kloks [J. Algorithms, 1996] solves the following problem in linear fixed-parameter time: given a tree decomposition of a graph of (possibly…