16 citations · 188 across the 122 of their papers we have counts for
8 papers · 1 filter
A Note on the Parameterised Complexity of Coverability in Vector Addition Systems
Michał Pilipczuk, Sylvain Schmitz, Henry Sinclair-Banks
We investigate the parameterised complexity of the classic coverability problem for vector addition systems (VAS): given a finite set of vectors , an initi…
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…
Isolation schemes for problems on decomposable graphs
Jesper Nederlof, Michał Pilipczuk, Céline M. F. Swennenhuis +1
The Isolation Lemma of Mulmuley, Vazirani and Vazirani [Combinatorica'87] provides a self-reduction scheme that allows one to assume that a given instance of a problem has a unique…
Integer Programming and Incidence Treedepth
Eduard Eiben, Robert Ganian, Dušan Knop +3
Recently a strong connection has been shown between the tractability of integer programming (IP) with bounded coefficients on the one side and the structure of its constraint matri…
Subexponential-time algorithms for finding large induced sparse subgraphs
Jana Novotná, Karolina Okrasa, Michał Pilipczuk +3
Let and be hereditary graph classes. Consider the following problem: given a graph , find a largest, in terms of the number of vertices…
On space efficiency of algorithms working on structural decompositions of graphs
Michał Pilipczuk, Marcin Wrochna
Dynamic programming on path and tree decompositions of graphs is a technique that is ubiquitous in the field of parameterized and exponential-time algorithms. However, one of its d…
Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems
Ivan Bliznets, Marek Cygan, Pawel Komosa +2
In this work, we focus on several completion problems for subclasses of chordal graphs: Minimum Fill-In, Interval Completion, Proper Interval Completion, Threshold Completion, and…
Subexponential fixed-parameter tractability of cluster editing
Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk +2
In the Correlation Clustering, also known as Cluster Editing, we are given an undirected n-vertex graph G and a positive integer k. The task is to decide if G can be transformed in…