16 citations · 188 across the 122 of their papers we have counts for
6 papers · 1 filter
A Polynomial Kernel for Trivially Perfect Editing
Pål Grønås Drange, Michał Pilipczuk
We give a kernel with vertices for Trivially Perfect Editing, the problem of adding or removing at most edges in order to make a given graph trivially perfect. This an…
Hitting forbidden subgraphs in graphs of bounded treewidth
Marek Cygan, Dániel Marx, Marcin Pilipczuk +1
We study the complexity of a generic hitting problem H-Subgraph Hitting, where given a fixed pattern graph and an input graph , the task is to find a set …
Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints
Ariel Gabizon, Daniel Lokshtanov, Michal Pilipczuk
In parameterized complexity, it is a natural idea to consider different generalizations of classic problems. Usually, such generalization are obtained by introducing a "relaxation"…
Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth
Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk +1
We give a fixed-parameter tractable algorithm that, given a parameter and two graphs , either concludes that one of these graphs has treewidth at least , or determi…
A subexponential parameterized algorithm for Proper Interval Completion
Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk +1
In the Proper Interval Completion problem we are given a graph G and an integer k, and the task is to turn G using at most k edge additions into a proper interval graph, i.e., a gr…
A subexponential parameterized algorithm for Interval Completion
Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk +1
In the Interval Completion problem we are given a graph G and an integer k, and the task is to turn G using at most k edge additions into an interval graph, i.e., a graph admitting…