16 citations · 188 across the 122 of their papers we have counts for
16 papers · 1 filter
Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments
Jana Cslovjecsek, Michał Pilipczuk, Karol Węgrzycki
In the Maximum Weight Independent Set of Rectangles problem (MWISR) we are given a weighted set of axis-parallel rectangles in the plane. The task is to find a subset of pairwi…
On digraphs without onion star immersions
Łukasz Bożyk, Oscar Defrain, Karolina Okrasa +1
The -onion star is the digraph obtained from a star with leaves by replacing every edge by a triple of arcs, where in triples we orient two arcs away from the center, a…
Fixed-parameter tractability of Graph Isomorphism in graphs with an excluded minor
Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk +1
We prove that Graph Isomorphism and Canonization in graphs excluding a fixed graph as a minor can be solved by an algorithm working in time , where is s…
Highly unbreakable graph with a fixed excluded minor are almost rigid
Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk +1
A set in a graph is -unbreakable if every separation of order at most in satisfies or . In this…
On Rational Recursive Sequences
Lorenzo Clemente, Maria Donten-Bury, Filip Mazowiecki +1
We study the class of rational recursive sequences (ratrec) over the rational numbers. A ratrec sequence is defined via a system of sequences using mutually recursive equations of…
Polynomial kernel for immersion hitting in tournaments
Łukasz Bożyk, Michał Pilipczuk
For a fixed simple digraph without isolated vertices, we consider the problem of deleting arcs from a given tournament to get a digraph which does not contain as an immersi…
Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters
Hans L. Bodlaender, Carla Groenland, Michał Pilipczuk
We investigate the parameterized complexity of Binary CSP parameterized by the vertex cover number and the treedepth of the constraint graph, as well as by a selection of related m…
Twin-width and types
Jakub Gajarský, Michał Pilipczuk, Wojciech Przybyszewski +1
We study problems connected to first-order logic in graphs of bounded twin-width. Inspired by the approach of Bonnet et al. [FOCS 2020], we introduce a robust methodology of local…
On the Complexity of Problems on Tree-structured Graphs
Hans L. Bodlaender, Carla Groenland, Hugo Jacob +2
In this paper, we introduce a new class of parameterized problems, which we call XALP: the class of all parameterized problems that can be solved in time and $f(k)\l…
Independence number of intersection graphs of axis-parallel segments
Marco Caoduro, Jana Cslovjecsek, Michał Pilipczuk +1
We prove that for any triangle-free intersection graph of axis-parallel segments in the plane, the independence number of this graph is at least . W…
Computing treedepth in polynomial space and linear fpt time
Wojciech Nadara, Michał Pilipczuk, Marcin Smulewicz
The treedepth of a graph is the least possible depth of an elimination forest of : a rooted forest on the same vertex set where every pair of vertices adjacent in is bou…
Dynamic data structures for parameterized string problems
Jędrzej Olkowski, Michał Pilipczuk, Mateusz Rychlicki +2
We revisit classic string problems considered in the area of parameterized complexity, and study them through the lens of dynamic data structures. That is, instead of asking for a…
Transducing paths in graph classes with unbounded shrubdepth
Michał Pilipczuk, Patrice Ossona de Mendez, Sebastian Siebertz
Transductions are a general formalism for expressing transformations of graphs (and more generally, of relational structures) in logic. We prove that a graph class ca…
Graphs of bounded twin-width are quasi-polynomially -bounded
Michał Pilipczuk, Marek Sokołowski
We prove that for every there is a constant such that every graph with twin-width at most and clique number has chromatic number bounded by $2^{γ_t…
Treelike decompositions for transductions of sparse graphs
Jan Dreier, Jakub Gajarský, Sandra Kiefer +2
We give new decomposition theorems for classes of graphs that can be transduced in first-order logic from classes of sparse graphs -- more precisely, from classes of bounded expans…
Bounding generalized coloring numbers of planar graphs using coin models
Jesper Nederlof, Michał Pilipczuk, Karol Węgrzycki
We study Koebe orderings of planar graphs: vertex orderings obtained by modelling the graph as the intersection graph of pairwise internally-disjoint discs in the plane, and orderi…