16 citations · 188 across the 122 of their papers we have counts for
11 papers · 1 filter
Model-Checking on Ordered Structures
Kord Eickmeyer, Jan van den Heuvel, Ken-ichi Kawarabayashi +6
We study the model-checking problem for first- and monadic second-order logic on finite relational structures. The problem of verifying whether a formula of these logics is true on…
Progressive Algorithms for Domination and Independence
Grzegorz Fabiański, Michał Pilipczuk, Sebastian Siebertz +1
We consider a generic algorithmic paradigm that we call progressive exploration, which can be used to develop simple and efficient parameterized graph algorithms. We identify two m…
Tight complexity lower bounds for integer linear programming with few constraints
Dušan Knop, Michał Pilipczuk, Marcin Wrochna
We consider the ILP Feasibility problem: given an integer linear program , where is an integer matrix with rows and columns and is a vector…
First-order interpretations of bounded expansion classes
Jakub Gajarský, Stephan Kreutzer, Jaroslav Nešetřil +4
The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-che…
Randomized contractions meet lean decompositions
Marek Cygan, Paweł Komosa, Daniel Lokshtanov +4
We show an algorithm that, given an -vertex graph and a parameter , in time finds a tree decomposition of with the following properties: *…
Enumerating minimal dominating sets in -free graphs and variants
Marthe Bonamy, Oscar Defrain, Marc Heinrich +2
It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we investigate this problem in graph cl…
Kernelization and approximation of distance- independent sets on nowhere dense graphs
Michał Pilipczuk, Sebastian Siebertz
For a positive integer , a distance- independent set in an undirected graph is a set of vertices pairwise at distance greater than , while a distance…
Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
Michał Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese
We consider two optimization problems in planar graphs. In Maximum Weight Independent Set of Objects we are given a graph and a family of objects, each being a co…
Polynomial bounds for centered colorings on proper minor-closed graph classes
Michał Pilipczuk, Sebastian Siebertz
For , a coloring of the vertices of a graph is {\em{-centered}} if for every connected subgraph~ of , either receives more than colors und…
Parameterized circuit complexity of model checking first-order logic on sparse structures
Michał Pilipczuk, Sebastian Siebertz, Szymon Toruńczyk
We prove that for every class of graphs with effectively bounded expansion, given a first-order sentence and an -element structure whose Gaifman graph belon…
Definable decompositions for graphs of bounded linear cliquewidth
Mikołaj Bojańczyk, Martin Grohe, Michał Pilipczuk
We prove that for every positive integer k, there exists an MSO_1-transduction that given a graph of linear cliquewidth at most k outputs, nondeterministically, some cliquewidth de…