121 citations · 375 across the 53 of their papers we have counts for
4 papers · 2 filters
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…
Bandwidth and Distortion Revisited
Marek Cygan, Marcin Pilipczuk
In this paper we merge recent developments on exact algorithms for finding an ordering of vertices of a given graph that minimizes bandwidth (the BANDWIDTH problem) and for finding…
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…