16 citations · 188 across the 122 of their papers we have counts for
11 papers · 1 filter
Neighborhood complexity and kernelization for nowhere dense classes of graphs
Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer +4
We prove that whenever is a graph from a nowhere dense graph class , and is a subset of vertices of , then the number of subsets of that are realized as…
Approximation and parameterized algorithms for geometric independent set with shrinking
Michał Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese
Consider the Maximum Weight Independent Set problem for rectangles: given a family of weighted axis-parallel rectangles in the plane, find a maximum-weight subset of non-overlappin…
Below all subsets for Minimal Connected Dominating Set
Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh
A vertex subset in a graph is a dominating set if every vertex not contained in has a neighbor in . A dominating set is a connected dominating set if the subgrap…
Hardness of approximation for strip packing
Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk +1
Strip packing is a classical packing problem, where the goal is to pack a set of rectangular objects into a strip of a given width, while minimizing the total height of the packing…
Linear kernels for edge deletion problems to immersion-closed graph classes
Archontia C. Giannopoulou, Michał Pilipczuk, Dimitrios M. Thilikos +2
Suppose is a finite family of graphs. We consider the following meta-problem, called -Immersion Deletion: given a graph and integer , decide wheth…
Tight lower bounds for the complexity of multicoloring
Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk +2
In the multicoloring problem, also known as (:)-coloring or -fold coloring, we are given a graph G and a set of colors, and the task is to assign a subset of color…
The Generalised Colouring Numbers on Classes of Bounded Expansion
Stephan Kreutzer, Michał Pilipczuk, Roman Rabinovich +1
The generalised colouring numbers , , and were introduced by Kierstead and Yang as generalisations of the usual colouring…
Cutwidth: obstructions and algorithmic aspects
Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond +2
Cutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges betw…
Hardness of approximation for H-free edge modification problems
Ivan Bliznets, Marek Cygan, Pawel Komosa +1
The -Free Edge Deletion problem asks, for a given graph and an integer , whether it is possible to delete at most edges from to make it -free, that is, not con…
Definability equals recognizability for graphs of bounded treewidth
Mikołaj Bojańczyk, Michał Pilipczuk
We prove a conjecture of Courcelle, which states that a graph property is definable in MSO with modular counting predicates on graphs of constant treewidth if, and only if it is re…
Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering
Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx +3
We prove the following theorem. Given a planar graph and an integer , it is possible in polynomial time to randomly sample a subset of vertices of with the following…