46 citations · 59 across the 12 of their papers we have counts for
15 papers
Sitting closer to friends than enemies, revisited
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk +1
Signed graphs, i.e., undirected graphs with edges labelled with a plus or minus sign, are commonly used to model relationships in social networks. Recently, Kermarrec and Thraves i…
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…
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,…
Dominating Set is Fixed Parameter Tractable in Claw-free Graphs
Marek Cygan, Geevarghese Philip, Marcin Pilipczuk +2
We show that the dominating set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (K(1,3)), the complete bipartite gr…
The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem)
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk +1
One of the driving problems in the CSP area is the Dichotomy Conjecture, formulated in 1993 by Feder and Vardi [STOC'93], stating that for any fixed relational structure G the Cons…