121 citations · 375 across the 53 of their papers we have counts for
10 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…
On Problems as Hard as CNFSAT
Marek Cygan, Holger Dell, Daniel Lokshtanov +6
The field of exact exponential time algorithms for NP-hard problems has thrived over the last decade. While exhaustive search remains asymptotically the fastest known algorithm for…
Steiner Forest Orientation Problems
Marek Cygan, Guy Kortsarz, Zeev Nutov
We consider connectivity problems with orientation constraints. Given a directed graph and a collection of ordered node pairs let $P[D]=\{(u,v) \in P: D {contains a} uv{-pa…
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…
Parameterized Complexity of Firefighting Revisited
Marek Cygan, Fedor V. Fomin, Erik Jan van Leeuwen
The Firefighter problem is to place firefighters on the vertices of a graph to prevent a fire with known starting point from lighting up the entire graph. In each time step, a fire…
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…
Channel Assignment via Fast Zeta Transform
Marek Cygan, Łukasz Kowalik
We show an O*((l+1)^n)-time algorithm for the channel assignment problem, where l is the maximum edge weight. This improves on the previous O*((l+2)^n)-time algorithm by Kral, as 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,…
Approximation Algorithms for Union and Intersection Covering Problems
Marek Cygan, Fabrizio Grandoni, Stefano Leonardi +3
In a classical covering problem, we are given a set of requests that we need to satisfy (fully or partially), by buying a subset of items at minimum cost. For example, in the k-MST…