Homepage: Michał Pilipczuk

About me

I am a PhD student of prof. Fedor Fomin at the University of Bergen; I started my studies in September 2011. The scope of my research consists of fixed-parameter tractability, kernelization, exact algorithms for NP-hard problems and, in fact, any nice combinatorial algorithmic problems that I encounter. I've done my masters in CS at the Faculty of Mathematics, Informatics and Mechanics of University of Warsaw, where I still pursue the master degree in mathematics.

Apart from this, I used to be involved in Polish Mathematical Olympiad. Despite moving to Norway, I still do some olympic stuff, including participation in selection of the problems and, occasionally, coaching some team for some international competition. I was working also as a jury member for Polish Olympiad in Informatics and a few times helped to prepare the collegiate algorithmic contest Potyczki Algorytmiczne (Algorithmic Engagements).

Contact Info

Teaching

Spring 2012: teaching assistance for INF 236 Parallelle algoritmer course.

If you have any troubles or questions regarding the course, send me an e-mail or drop by at the office 3146. I will put some stuff from the exercise sessions here.

Spring 2012: random lectures on ACM stuff. Subpage here.

Papers

Unpublished

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk,
Known algorithms for Edge Clique Cover are probably optimal,
unpublished, available at [arxiv]

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
Sitting closer to friends than enemies, revisited,
unpublished, available at [arxiv]

Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Yngve Villanger,
Subexponential fixed-parameter tractability of cluster editing,
unpublished, available at [arxiv]

Fedor V. Fomin, Michał Pilipczuk,
Jungles, bundles, and fixed parameter tractability,
unpublished, available at [arxiv]

Accepted

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk,
On group feedback vertex set parameterized by the size of the cutset,
accepted to WG 2012 (best student paper award), available at [arxiv]

Petr Golovach, Pinar Heggernes, Pim van 't Hof, Fredrik Manne, Daniël Paulusma, Michał Pilipczuk,
How to eliminate a graph,
accepted to WG 2012

Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström,
Clique cover and graph separation: New incompressibility results,
accepted to ICALP 2012 (track A), available at [arxiv]

Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström,
Fixed-parameter tractability of multicut in directed acyclic graphs,
accepted to ICALP 2012 (track A), available at [arxiv]

Fedor V. Fomin, Petr Golovach, Jesper Nederlof, Michał Pilipczuk,
Minimizing Rosenthal potential in multicast games,
accepted to ICALP 2012 (track C)

Published

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
Solving the 2-Disjoint Connected Subgraphs problem faster than 2ⁿ,
LATIN 2012

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
Scheduling partially ordered jobs faster than 2ⁿ,
ESA 2011, available at [arxiv]

Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh,
On the hardness of losing width,
IPEC 2011

Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh,
On cutwidth parameterized by vertex cover,
IPEC 2011

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
On Multiway Cut parameterized above lower bounds,
IPEC 2011, available at [arxiv]

Marek Cygan, Michał Pilipczuk, Riste Škrekovski,
On the inequality between radius and Randić index for graphs,
MATCH Commun. Math. Comput. Chem., Volume 67 (2012) number 2

Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Ildikó Schlotter,
Parameterized Complexity of Eulerian Deletion Problems,
WG 2011

Michał Pilipczuk,
Problems parameterized by treewidth tractable in single exponential time: a logical approach,
MFCS 2011, available at [arxiv]

Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk,
Solving connectivity problems parameterized by treewidth in single exponential time,
FOCS 2011, full (really full) version available at [arxiv]

Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
Dominating Set is Fixed Parameter Tractable in Claw free Graphs,
TCS 412(50), available at [arxiv]

Marek Cygan, Michał Pilipczuk, Riste Škrekovski,
Relation between Randić index and average distance of trees,
MATCH Commun. Math. Comput. Chem., Volume 66 (2011) number 2

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem),
SODA 2011, available at [arxiv], journal version accepted to SICOMP

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
Subset feedback vertex set is fixed parameter tractable,
ICALP 2011 (track A), available at [arxiv]

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
Improved FPT algorithm and quadratic kernel for Pathwidth One Vertex Deletion,
IPEC 2010, journal version in Algorithmica

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk,
Kernelization hardness of connectivity problems in d-degenerate graphs,
WG 2010, journal version accepted to DAM

Presentations

Here you can find a random subset of my presentations, which by some chance I have found in the final version. Description in Polish means that the content is also in Polish.

Problems

The list of problems in programming competitions I am a (co)author of.

Other