16 citations · 188 across the 122 of their papers we have counts for
3 papers · 1 filter
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…
Subset feedback vertex set is fixed parameter tractable
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk +1
The classical Feedback Vertex Set problem asks, for a given undirected graph G and an integer k, to find a set of at most k vertices that hits all the cycles in the graph G. Feedba…