16 citations · 188 across the 122 of their papers we have counts for
8 papers · 1 filter
On group feedback vertex set parameterized by the size of the cutset
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk
We study the parameterized complexity of a robust generalization of the classical Feedback Vertex Set problem, namely the Group Feedback Vertex Set problem; we are given a graph G…
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…
Jungles, bundles, and fixed parameter tractability
Fedor V. Fomin, Michał Pilipczuk
We give a fixed-parameter tractable (FPT) approximation algorithm computing the path-width of a tournament, and more generally, of a semi-complete digraph. Based on this result, we…
Clique cover and graph separation: New incompressibility results
Marek Cygan, Stefan Kratsch, Marcin Pilipczuk +2
The field of kernelization studies polynomial-time preprocessing routines for hard problems in the framework of parameterized complexity. Although a framework for proving kerneliza…
Scheduling partially ordered jobs faster than 2^n
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk +1
In the SCHED problem we are given a set of n jobs, together with their processing times and precedence constraints. The task is to order the jobs so that their total completion tim…
On Multiway Cut parameterized above lower bounds
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk +1
In this paper we consider two above lower bound parameterizations of the Node Multiway Cut problem - above the maximum separating cut and above a natural LP-relaxation - and prove…
Problems parameterized by treewidth tractable in single exponential time: a logical approach
Michał Pilipczuk
We introduce a variant of modal logic, dubbed EXISTENTIAL COUNTING MODAL LOGIC (ECML), which captures a vast majority of problems known to be tractable in single exponential time w…
Solving connectivity problems parameterized by treewidth in single exponential time
Marek Cygan, Jesper Nederlof, Marcin Pilipczuk +3
For the vast majority of local graph problems standard dynamic programming techniques give c^tw V^O(1) algorithms, where tw is the treewidth of the input graph. On the other hand,…